Wait...DH, I think you're getting yourself confused here. It is still entirely possible to jailbreak a 3.1.2 3GS with the new bootrom using redsn0w. Redsn0w does not require a restore, nor does it require previous jailbreaking. It is not possible to use PwnageTool or a custom firmware to jailbreak such a phone on 3.1.3; pwnage tool requires that a phone be pwned, and a 3GS with the new bootrom cannot be pwned.
Also, once you have jailbroken with redsn0w, it is easy to put in your request SHSH request in Cydia; Saurik is not saving 3.1.3 hashes yet, but as soon as he does he will get it. You do not have to be on the 3.1.3 firmware for Saurik to request and save your 3.1.3 SHSH.
OP: You can jailbreak your phone on 3.1.2 using redsn0w or blackra1n (I suggest redsn0w), not PwnageTool. Do not upgrade to 3.1.3. You will have a tethered jailbreak. You can also unlock using blacksn0w. Be aware that if you ever need to restore your phone you will be forced to restore to 3.1.3 and lose your ability to jailbreak and unlock. Because you don't have your 3.1.2 SHSH on file with Saurik (and it is too late to get it on file), you will not be able to restore to 3.1.2. So be careful what you do with your phone.