I have two iphones, both 3gs. Both are at Firmware 3.1.3 (7e18) and both have a baseband of 05.12.01 . One is already jailbroken, and the other is not.

Well it seriously has been a whole year since I last looked into the JB scene. I would like some quick assistance on Jailbreaking AND Unlocking both iphone 3gs.

Can someone give me detailed instructions or at least point me towards the right direction? Thanks!

You need to check if these have saved SHSH for any iOS versions. Use tinyumbrella to do that.
Also check bootrom version (explained 100s of times, search for a guide)
Finally do you have access to a mac to use Pwnagetool? (sn0wbreeze is also an option but we try not to support or recommend it as older versions had problems)

Then you need to decide which iOS version you can realistically install and jailbreak. (With custom IPSW from pwnagetool or sn0wbreeze, you can definitely jailbreak/unlock 4.3.1 on both, but I recommend trying for 4.2.1 if you have the correct saved SHSH)