Tested with CM7 rom ( rooted Nexus Hero )

connect your Android to linux box via USB

Find your external ( rmnet0 / tiwlan0 ) ipaddress:
Method 1:
note your rmnet0 / tiwlan0 / = public ip address

Method 2:
adb shell
#busybox ifconfig
note your rmnet0 ip address

( if you are connected to the internet via wifi , subsitute tiwlan0 for rmnet0 )

on your Android:
start USB tethering

in BT4 / linux..
#ifconfig usb0 up

open WiCD,
set wired interface to usb0
set DNS1 to your rmnet0 ipaddress

enjoy interwebs!