Use RedSn0w. Go to Extras > Custom IPSW. Select the iOS 6.1.3 IPSW for the 3GS. A pop-up should come up saying that you can use the Restore feature. If needed, select the iOS 6.1.3 IPSW for the 3GS again, and for blobs, select remote (don't think you have to do this, but just in case). A pop-up should come up asking if you want to preserve your baseband, say that you do. Then a prompt will ask you to put your device into DFU mode to Pwned DFU it. Follow the prompts from RedSn0w. Once the restoration is complete, use a Recovery Fix to get yourself out of Recovery Mode.
Remember that iOS 6.1.1-6.1.3 does not have an UltraSn0w Fixer, so you can't use UltraSn0w, which is why I recommend that 3GS users stay on iOS 5 when relying on UltraSn0w.