Update : iBooty has been updated to v1.6 ! Added a video tutorial. 


iH8sn0w has posted a process quite complex to jailbreak iOS 4 for iPhone 3GS with new iBoot.
This jailbreak based on the creation of a custom firmware using Sn0wbreeze, that you will install thanks to a new tool iBooty from iH8sn0w.

iPhone 3GS, find the version of your iBoot.
For old iBoot, follow this guide.
For iPhone 3GS with new iBoot, this tutorial concerns you !

Required :

• iPhone 3GS New iBoot. [Mac only]
• Have your ECID (shsh) signed for FW 3.1.2 only on Saurik server.
• IBSS Grabber
• Payload Pwner rc6
• iBooty 1.6
• Sn0Wbreeze 1.6.2
• Libusb (links below)
• Firmwares 3.1.2 and 4.0
• iTunes 9.2

Warning Note: All the standard warnings apply. This is for advanced users only. Only proceed if you think you know your iPhone inside out.

Required : 

xpwntool
iOS 3.1.2, 4.0
iOS 3.1.2 SHSH blobs
=>> Download this

STEP 1 : Grabbing your 3.1.2 iBSS file. 

Pointing your hosts :
I : If you have your shsh blobs saved on Cydia/Saurik’s server then follow this tutorial.  
II : If you have it saved with TinyUmbrella, then download the GUI here.   

Restoring to grab the iBSS file. 

I : Place your device in DFU.
II : Start up the iBSS/iBEC grabber.
III : Put the save folder on a new folder on your desktop.
IV : Hit "Start Monitoring".
V : Now go back to iTunes and do SHIFT + Restore. Then browse for your 3.1.2 IPSW. You will need to restore to 3.1.2 in order to pwn 4.0.

STEP 2: Creating your custom firmware 

Use Pwnage Tool to create a custom ipsw ignore the warnings about the new bootrom. 

STEP 3:
Extract the zip file we downloaded earlier and use terminal to enter it
STEP 4:
Create a new folder inside this called 3.1.2 and extract your 3.1.2 ipsw here (unzip *.ipsw in terminal)
STEP 5:
Use xpwntool to patch iBoot & iBSS (run this in terminal)

xpwntool Firmware/dfu/iBSS.n88ap.RELEASE.dfu ibss.d -iv 41639d34547ae3dd7921bf3539dba529 -k 9121de4a038675d92e1a28683b2138b7a3bdb80994273d090398051c7f5af53c; bspatch ibss.d ../exploitibss312 ../ibss.patch; xpwntool Firmware/all_flash/all_flash.n88ap.production/iBoot.n88ap.RELEASE.img3 iboot.d -iv 127aa60e77da219961ee70707f44cbd4 -k c72ab4aae971f3a9ec356dfe555e4aef72d8e96c480698445ac236904e6a3443; bspatch iboot.d ../iboot.payload ../iboot.patch; cd ..; rm -rf 3.1.2

STEP 6:
Create a folder called 4.0_cust inside 4.0_pwn and enter it with terminal and copy your custom 4.0 ipsw here.
STEP 7:
Extract your custom ipsw (unzip *.zip)
STEP 8:
Run the following in terminal:

cp kernelcache.release.n88 ../kcache.40; cp Firmware/dfu/iBEC.n88ap.RELEASE.dfu ../iBEC.40; cd ..;

STEP 9:
Copy your signed iBSS from earlier into 4.0_pwn
STEP 10:
Place your device in DFU mode (power home for 10 seconds, release power keep holding home (blank screen and itunes asking to restore).
STEP 11:
Run the following in terminal:

./irecovery -u ibss312.dfu; ./irecovery -r; sleep 10; ./irecovery -e exploitibss312; ./irecovery -u iBEC.40; ./irecovery -c go; sleep 10; ./irecovery -u sn0w.img3; ./irecovery -c "setpicture 0"; ./irecovery -c "bgcolor 1 1 1";

STEP 12:
Restore your custom 4.0 ipsw
Booting your device:
Run the following in terminal (once in the 4.0_pwn directory):

./irecovery -u ibss312.dfu; ./irecovery -r; sleep 10; ./irecovery -e exploitibss312; ./irecovery -u iBEC.40; ./irecovery -c go; sleep 10; ./irecovery -u sn0w.img3; ./irecovery -c "setpicture 0"; ./irecovery -c "bgcolor 1 1 1"; ./irecovery -u kcache.40; ./irecovery -c bootx;

iTunes will detect your device several times before it boots.
PS: When i wake up i will write a script to automate most of this.

Once you have jailbroken your phone, you can unlock it using ultrasn0w 0.93 (on any baseband), guide for which is posted here.