A method of “hacking” the 3G/3GS for tethering has been found but you need to be jail broken 1st.

Instructions are HERE and I accept no responsibility if it breaks your iPhone (you may have to reinstall again if you break it).

Also I have copied the instructions here:

• First get this file and put CommCenter.patch on your Desktop:
  3GS: http://iphwn.org/CommCenter_3gs_312.zip
  3G: http://iphwn.org/CommCenter_3g_312.zip
• Copy /System/Library/PrivateFrameworks/CoreTelephony.framework/Support/CommCenter to your Desktop also.
  Open the Terminal and:
  cd Desktop
• bspatch CommCenter CommCenter-hacked CommCenter.patch
• Now go ahead and delete CommCenter now from your Desktop and rename CommCenter-hacked to just CommCenter.
• Rename CommCenter on your iPhone to CommCenter.backup in case something bad happens, so you have a backup.
• Copy the new CommCenter to your iPhone.
• SSH into your iPhone or use MobileTerminal as root and chmod +755 the new CommCenter so that it’s executable.
• Restart your phone.

It simply removes the test for testing for the tethering signature thus enabling tethering on your iPhone 3G/3GS on 3.1.2 firmware.

After you have done this go to http://www.unlockit.co.nz on your iPhone and download the config for your carrier.