At the moment only a tethered jailbreak is available for newer bootrom 3GS models. Redsn0w is the best tool to use in my opinion. If you check the dev team blog you'll see that they will most likely not be releasing any other jailbreaks for 3.1.2 or 3.1.3. The reasoning being that they don't want to waste bugs in the OS on a minor maintenance release and instead are saving the next jailbreak method for the next major OS update (if that).
Originally Posted by flav
For what it's worth, my experience with a tethered jailbreak has not been bad at all. I installed all the things that required a reboot at the begining and now I have no further need to restart my phone. If this is not your situation and you have the need to frequently or regularly restart/shutdown the phone than a tethered jailbreak may not be for you. In this case you'll likely have to wait for the next big Apple OS update.