Just received a friends old 3G which has never been jailbroken, it is currently on 4.0.1 with modem firmware 05.13.04. Can someone suggest my best approach for a JB and unlock, it currently has an official AT&T sim, but was hoping to use it with a t-mobile pay as you go. Thanks in advance
Since it's an iPhone 3G, I'd recommend to take it down to 3.1.3 or up to 4.2.1. iOS 4.0.x is awful on that phone.
BUT, if you'd rather stay on 4.0.1, Limera1n, Jailbreakme, and Redsn0w should do the trick. Jailbreakme is probably the fastest and easiest.
If you do want to take it down to 3.1.3, simply shift+restore to a stock 3.1.3 and you can jb with Jailbreakme as well after restoring.
If you want to take it up to 4.2.1 (or 4.1) you'll need a custom firmware created by PwnageTool. If you don't have a Mac, you'll have to find the custom firmware. Just make sure it doesn't package the iPad baseband upgrade into it. I'd really suggest taking it down to 3.1.3 over anything.