How to connect Android phone to Arduino?
You bet it's possible. I used a pretty cheap bluetooth module that I got from Amazon, and wrote an app using the information on the official Android Developers page to connect to the Arduino. There are many guides online telling you how to hook up a module to the pins of the duino. 

You can probably get a cheaper module if you look on eBay and don't care how long it takes to arrive, and I think there's at least one app on the Play store for controlling an Arduino if you can make it work for your purpose.

USB connections are probably possible, though I haven't done any of that.