OLD BOOTROM + Spirit => 4.0 JB

Updated for FW 4.0/4.0.1 + 'Star' jailbreak. You'll need NOR files from a custom 4.0 ipsw made with PwnageTool 4.0.1.
You still obviously need to have an old bootrom 3GS, however you don't currently need any SHSH while Apple still signs 4.0.1
The fact that Star jailbreak uses Safari, however, means it will be patched in weeks, so back up those hashes while you can..
Now that 4.0 is jailbroken, potential uses of this method include installing 4.1 betas, rolling back to 3.x and similar fun activities.

STOP if you have a new bootrom (week 40+, tethered only 3.1.2 JB etc). Here's how to check bootrom ver
- your hardware is iPhone 3GS with OLD BOOTROM
- you HAVE 3.1.3 SHSH (**)
- you DON'T have 3.1.2 SHSH (otherwise, just use blackra1n/redsn0w).
- you WANT iOS4/JB

Update: thanks to movie for those awesome step by step instructions!
Update2: someone made a Cydia package. Looking at type of questions people ask in the comments, that might be the only option for 80% of them. Apple's license terms, of course, don't allow to redistribute their binaries, so I just link to it. Their description also says it works with 3.1.2/Spirit - I very much doubt that.

This tool can be used to flash pwned nor files (containing LLB  exploit) on the phone  running Spirit JB  (script has hardcoded offsets for 3.1.3 3GS).

*Now flasher checks that all files exist before flashing them.
http://code.google.com/p/iphone-img3-flasher/downloads/detail?name=spirit2pwn_r2.zip

1. Unpack pwned(!) 3.1.3 firmware, copy all the files from  iPhone2,1_3.1.3_7E18_Custom_Restore\Firmware\all_flash\all_flash.n88ap.production folder to /tmp directory your phone. You can use CyberDuck or WinSCP to do that. Copy those files directly to the /tmp, not to a subfolder: LLB should be at /tmp/LLB.n88ap.RELEASE.img3, etc.!
2. Extract the contents of the spirit2pwn_r2.zip archive to /tmp directory on the phone.
3. Run the following commands on the iPhone: (Use ssh or PuTTY).

cd /tmp

chmod 755 pwn_old_boot_r2.sh
./pwn_old_boot_r2.sh

• Now reboot and your iboot and llb should be pwned, and you can restore to a custom FW now.

Thanks Gojohnnyboi for code, ZeRoLiMiT for testing ;)

(**) Technically, you can still do that if you don't have 3.1.3 SHSH, but then if you don't really have old bootrom or if you use wrong ipsw files, your only option will be to upgrade to 4.0 and stay without jailbreak or unlock until a new exploit is made public.