until recently i was stuck with a stock android 1.6 - and USB tethering was somewhat adventurous (Tetherbot was an option, connectbot another... both worked best, i.e. without restrictions, when there was a VPN tunneled 'over' either of them.)
now, this set-up can also be used the other way around (i.e. use the computer's internet connection the mobile is connected to). however, android's ConnectivityManager does not recognize this connection in such a way that services like Contacts Sync would get going.
startUsingNetworkFeature() in http://android.git.kernel.org/?p=platform/frameworks/base.git;a=blob;f=services/java/com/android/server/ConnectivityService.java will choke on android.net.NeworkInfo.isAvailable():
D/ConnectivityService( 166): getMobileDataEnabled returning true
D/ConnectivityService( 166): special network not available
D/ConnectivityService( 166): getMobileDataEnabled returning true
D/ConnectivityService( 166): special network not available