I was going to try the IOIO extension but its been on backorder for months at sparkfun. My next plan was to use bluetooth until I saw this today… Since FEZ has USB support, how tricky would this be to implement?
FEZ stand for Freakn Easy 
Blake already got accessory API to work …this will give you much more than IOIO board and better than hacking into the debug bridge. Make sure you watch the video http://www.tinyclr.com/forum/20/3212/
My phone is android 2.1 (upgraded from 1.5) and I believe you need 2.3.4 to use the accessory api.
Then use Blake’s code along whit the Arduino code to implement the debug bridge.
I’ve started implementing an ADB bridge for FEZ, some time ago. But after the Accessory API comes out I stopped the work. My Nexus One runs Android 2.3.4 now, so I don’t need the ADB stuff any more, but I can show you what I have done so far. Together with Blake’s code it should be easy to get it finished.
Hardest thing for me was to learn all the USB client stuff. But this can be helpfull for other projects.
I have uploaded my FEZ - ADB code here:
http://robotfreak.googlecode.com/files/FezBridge.zip
It’s uncompleted right now, it does the initial connect with the phone, but no data in/out at the moment.
Ok, I got bluetooth between the fez and android working but if you can get two way comm going and include the android code I’ll take a look at it as a replacement, would probably use less power. Did you make the USB cable? It would have to be a mini to micro plug do they even sell those?
You can’t do mini-to-micro (there is an adapter, but still requires a minor hardware change on the board), you would have to convert your FEZ to support USB Host, and write a custom driver to run ADB or Microbridge from the FEZ. At that point the fez is hosting the android device. RobotFreak is probably using the Domino, which comes with a USB Host port on it already.
Adding USB host to panda is not very difficult http://ghielectronics.blogspot.com/2011/03/usb-host-support-is-added-on-fez-panda.html