I hate to be the bearer of bad news, but it won't work. You confessed that Cydia doesn't have your SHSHs for older versions archived, and I'm guessing you did not personally archive them to your computer before 3.1.3 came out.
You cannot collect or generate SHSHs for versions of the firmware that have already been withdrawn by Apple. Period. You need to collect them BEFORE Apple withdraws them.
Sorry.
I would stick with 3.1 for now and just jailbreak it with blackra1n (I don't think redsn0w will jailbreak 3.1, just 3.1.2). Then go into Cydia once jailbroken and instruct Cydia to collect your 3.1.3 SHSHs from Apple. If 3.1 works for you okay, then stay with 3.1 and wait until someone figures out how to crack 3.1.3 on a 3GS.
If you happen to have an old bootrom 3GS (non-tethered jailbreak), then once jailbroken with blackra1n you could elect to create a custom 3.1.3 IPSW for your phone with PwnageTool and upgrade to that. Once you are jailbroken, never ever install official, non-pwned Apple firmware again (unless you have 3.1.3 SHSHs on file with Cydia and redsn0w for 3.1.3 comes out), otherwise you will be without jailbreak forever.
-- Nathan
EDIT: Heck, if you'd rather use 3.1.2 than 3.1.3, once you jailbreak with blackra1n on 3.1 you can also make a 3.1.2 firmware file with PwnageTool and use that. Apple doesn't have to sign off on custom IPSWs on a pwned phone.
