In this guide i will a demonstrate a way to connect your android phone to the internet using just the usb cable. This will only work on rooted phones with a terminal emulator installed.
Connect your android phone to the linux box via USB and then go to Settings > Wireless & networks > Tethering & portable hotspot and enable USB tethering.
Disable any wi-fi or 3g connection from your android phone.
On your linux box, run the following command as root.
ifconfig usb0 192.168.42.135 up
Install and run a firewall program called firestarter and enable internet connection sharing for usb0 as shown below.
Run your android terminal emulator and execute the following commands.
ifconfig usb0 192.168.42.130 up
busybox ifconfig usb0 192.168.42.130 up
route add -net default gw 192.168.42.135 usb0
busybox route add -net default gw 192.168.42.135 usb0