There doesn't seem to be a definitive solution out there for doing this, so I went out and figured it out on my own. This will jailbreak and unlock an iPhone 3GS with older bootrom and modem firmware 05.13.04. I'm assuming you already have iOS4 installed. *Before starting you should edit the 'hosts' file in the /etc/ directory to include the string: "126.96.36.199 gs.apple.com". This will avoid any Apple activation server errors. 1. You'll need to download the latest (4.01) Pwnage tool and pwn the 4.0 .ipsw for the iPhone 3GS. 2. Download the 3.1.2 iPhone 3GS .ipsw, Recboot, and Blackra1n. 3. Plug in the iPhone and force it into recovery mode via Recboot. 4. Option-click restore in iTunes and select the 3.1.2 .ipsw and continue with the restore. 5. Upon completion (and iTunes error) use Recboot Exit to release the iPhone from recovery mode. *At this point you should have 3.1.2 running on the iPhone. 6. Run Blackra1n to jailbreak the iPhone, and then download Cydia. 7. Repeat steps 3-5 but this time select the custom 4.0 .ipsw outputted by Pwnage tool. 8. In Cydia, install the latest (0.93) ultrasn0w. 9. Cross your fingers and hope for the best. I hope this helps some of you struggling with this.