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).