ATTiny85 and USB with Android?
Take a look at V-USB. I've used it with ATtiny85. It's essentially a firmware-only USB implementation for AVRs that don't have "built-in" USB.

The V-USB site also has a decent list of example projects you could use as a starting point. Not sure about how/if you can interface with android or not.

One thing to be aware of is their licensing model. You have to pick either GPL or commercial license. If you don't want to bother with adhering to GPL their commercial option has a "hobby" license for $9.90.