I noticed some apps have a link to a Youtube video instead of a screenshot in Google's Android Play store. How can I make a video of my Android game running on a physical device? The emulator won't work for me (my game uses the camera preview feed). I guess I could take a video of the phone with another device, but that seems a little cheesy to me.
There are programs available to capture video on the physical device. See this question about that. Beyond that, I think you have an opportunity here to not just make a video capture of your game, but to make a trailer. Check out this article on making video game trailers to see what time/resources you have to making a excellent trailer.
Some phones(or tablets) have an HDMI output, you can connect your HDMI cable to a video recorder linked to your PC.