How can I get the trace of dalvik bytecode that is being executed while the device is running an app (like logcat does)?
There is no existing tool to do what you want, but it might be possible to implement such a tool without too much work.
The general idea is that you want to connect to dalvik's vm as a debugger, using the jdwp protocol, and single step the virtual machine, inspecting the state between each step and printing out the instruction. You should be able to get the... instruction index. Or maybe the instruction offset, via JDWP.
Additionally, you will need to read the dex file, and look up the exact instruction being executed, based on the instruction index/offset you get from JDWP.
You should be able to use AndBug to implement the first part of the above solution, and then use dexlib to access the dex file, in order to get the instruction.