I tried to get my raspi online by plugging it into my Nexus 4 via USB, then enabling USB tethering under Android's wireless settings dialog. The 'usb0' interface appeared briefly with ifconfig, but dmesg revealed that the phone was connecting and disconnecting itself about once a second: lots of "usb disconnect" messages and stuff about unregister rndis_host.
My best guess is that it's something to do with broken USB OTG support, since the "charging" notification on the lock screen kept flickering on and off. Super lame.
Switching over to a Nexus 7 tablet, USB tethering worked just as expected; plug it in, make sure USB tethering is enabled on the android side, then "sudo dhclient usb0" on the raspi side.