iPhone 3G on 3.1.3, help please

[bigmac02]

I've got an iphone 3G currently on 3.1.3 and it is not jailbroken.
However, I would like to use it on another carrier but also update it to 4.1. What would be my best solution?

[i.Annie]

Currently on 3.1.3, jailbreak it with Redsn0w 0.9.4 (download the 3.1.2 ipsw to use with it).

Then after you've jb on 3.1.3, go download Sn0wbreeze 2.0.2 (off iH8sn0w.com). Get the 4.1 stock ipsw to use with it.

Create a custom fw with the 4.1 ipsw in Sn0wbreeze. When that's done, open iTunes.

Set phone into DFU mode and shift+restore to the custom fw. Make sure you don't accidentally select the stock fw or else you'll screw yourself out if the unlock.

After the restore to the custom fw, you should be on 4.1 jailbroken. Unlock with Ultrasn0w. Install it via Cydia.

Edit: I'm pretty sure you don't have to do the first step and jailbreak it with Redsn0w, but I haven't tested it myself so I just put that step there just in case. You can try skipping it if you'd like. Just note that if you choose to skip that step, and you receive an error during the restore, all you have to do is use iReb (from ih8sn0w.com) to bypass the errors.