Let me clear this upfront. The following instructions will only help downgrade iPhone 3G which is currently on iPhone OS 3.1.3 with 05.12.01 baseband and older bootloader 05.08. This wont work with iPhone 3GS.
If your iPhone meets the above criteria, you can then use the latest version of Fuzzyband which supports iPhone 3.1.3 to downgrade your 05.12.01 baseband to the older 04.26.08 even if you accidently upgraded to the stock iPhone OS 3.1.3 from iTunes. Once you have downgraded your baseband, you can then use ultrasn0w to unlock your iPhone on iPhone 3.1.3 firmware. Here’s how you do it.