After much frustration, I have finally managed to downgrade and re-jailbreak my 3GS. I've written a step-by-step guide and attempted this twice to confirm this works. Please let me know if this works for you. Also, if anyone is willing to try this method on any other iDevice, please let me know how it turns out. Hopefully, people will find this helpful and clear.
DOWNGRADE, JAILBREAK & UNLOCK
1. If you have attempted to downgrade from 3.1.3 previously, this method is almost guaranteed NOT to work UNLESS you do a fresh install of the 3.1.3 firmware via iTunes. Do this by holding the power & home key for a minute or so to put your phone into Recovery mode. Click Restore, then Restore & Update to 3.1.3.
2. Create a back-up of your iPhone. If this downgrade doesn't work, you can always go back to this version, and you'll be able to retreive your data in the process.
3. Bear in mind that if the downgrade is successful, you won't be able to access your backed-up content. You'll have to manually enter all your contact information, and drag all your pictures onto the device. Some may even want to note down what applications they have installed, so that they can re-download them again after the downgrade is complete.
4. On your iPhone, go to General > Settings > About. Under 'Model' note down whether this contains "MC" or not. If it contains "MC" then your iPhone is known as a later model. If not, it is an earlier model. It is important that you remember which your iPhone is.
5. Google "felixbruns", go to "iPod and iPhone Firmware Download" and download "iPhone 3G S (3.1.2/7011)". This will download a file called iPhone2,1_3.1.2_7D11_Restore.ipsw.
6. Google "redsn0w" and under 'Download Links' you will be able to download redsn0w 0.9.2.
7. Google blackra1n and download blackra1n.exe.
8. Find Notepad in your Start Menu, right click it, and select 'Run as administrator'.
9. In Notepad, go to File > Open and navigate to C:/Windows/System32/drivers/etc.
10. Still in Notepad, where it says "Text Documents (*.txt)" change this to "All Files (*.*)" and select 'hosts' from the files that appear.
11. Create a new line at the bottom of the file, and type this: 74.208.10.249 gs.apple.com
12. Save the file you have just edited.
13. Connect your iPhone if you haven't already, and while in iTunes, hold the Shift key on your keyboard and click the Restore button.
14. iTunes will then allow you to select a file. Navigate to iPhone2,1_3.1.2_7D11_Restore.ipsw which you downloaded in Step 5.
15. Allow iTunes to restore this file. It will show an error after attempting to restore - this is normal. Just click OK.
16. Again, hold Shift and click Restore, and select the same file again. It will display an error again. Just press OK, then close iTunes.
17. Now open the redsn0w RAR file which you downloaded in Step 6. You may need to install a program called WinRAR if you don't already have it on your computer in order to open the file. Run redsn0w.exe from the RAR file.
18. In redsn0w, click Browse and select iPhone2,1_3.1.2_7D11_Restore.ipsw.
19. A window will popup asking if you are using a newer iPhone. It is important that you select the correct option here. Remember: in Step 4, you had to note down whether your Model version contained "MC" or not. If they did, select Yes. If they didn't, select No.
20. On the next screen, ensure "Install Cydia" IS NOT ticked, and "Just boot tethered right now" IS selected. Then click Next. After a few seconds, you will be able to click Finish. Meanwhile, your iPhone is still working away. After about a minute, the screen will go blank as they keypad locks.
21. Now run blackra1n.exe which you downloaded in Step 7, and click "make it ra1n".
22. Connect to WiFi on your iPhone.
23. Run the blackra1n app which is now on the 2nd page of your iPhone apps. Select Cydia, Rock and sn0w, and then press Install.
24. If your iPhone picks up a network signal, this usually means your phone is now jailbroken and unlocked. If it does not pick up a signal and it is not due to you being in a poor signal area, this means the jailbreak did not work. Start from Step 1 and if you are still having issues, restore to your latest back-up.
Remember, if this method of jailbreaking does not work for you, it is not the end of the world. Don't get worked up about it if it fails; whatever happens, you still have a perfectly good iPod and web browser and a ton of free apps you can download from the App Store!
DOWNGRADE, JAILBREAK & UNLOCK
1. If you have attempted to downgrade from 3.1.3 previously, this method is almost guaranteed NOT to work UNLESS you do a fresh install of the 3.1.3 firmware via iTunes. Do this by holding the power & home key for a minute or so to put your phone into Recovery mode. Click Restore, then Restore & Update to 3.1.3.
2. Create a back-up of your iPhone. If this downgrade doesn't work, you can always go back to this version, and you'll be able to retreive your data in the process.
3. Bear in mind that if the downgrade is successful, you won't be able to access your backed-up content. You'll have to manually enter all your contact information, and drag all your pictures onto the device. Some may even want to note down what applications they have installed, so that they can re-download them again after the downgrade is complete.
4. On your iPhone, go to General > Settings > About. Under 'Model' note down whether this contains "MC" or not. If it contains "MC" then your iPhone is known as a later model. If not, it is an earlier model. It is important that you remember which your iPhone is.
5. Google "felixbruns", go to "iPod and iPhone Firmware Download" and download "iPhone 3G S (3.1.2/7011)". This will download a file called iPhone2,1_3.1.2_7D11_Restore.ipsw.
6. Google "redsn0w" and under 'Download Links' you will be able to download redsn0w 0.9.2.
7. Google blackra1n and download blackra1n.exe.
8. Find Notepad in your Start Menu, right click it, and select 'Run as administrator'.
9. In Notepad, go to File > Open and navigate to C:/Windows/System32/drivers/etc.
10. Still in Notepad, where it says "Text Documents (*.txt)" change this to "All Files (*.*)" and select 'hosts' from the files that appear.
11. Create a new line at the bottom of the file, and type this: 74.208.10.249 gs.apple.com
12. Save the file you have just edited.
13. Connect your iPhone if you haven't already, and while in iTunes, hold the Shift key on your keyboard and click the Restore button.
14. iTunes will then allow you to select a file. Navigate to iPhone2,1_3.1.2_7D11_Restore.ipsw which you downloaded in Step 5.
15. Allow iTunes to restore this file. It will show an error after attempting to restore - this is normal. Just click OK.
16. Again, hold Shift and click Restore, and select the same file again. It will display an error again. Just press OK, then close iTunes.
17. Now open the redsn0w RAR file which you downloaded in Step 6. You may need to install a program called WinRAR if you don't already have it on your computer in order to open the file. Run redsn0w.exe from the RAR file.
18. In redsn0w, click Browse and select iPhone2,1_3.1.2_7D11_Restore.ipsw.
19. A window will popup asking if you are using a newer iPhone. It is important that you select the correct option here. Remember: in Step 4, you had to note down whether your Model version contained "MC" or not. If they did, select Yes. If they didn't, select No.
20. On the next screen, ensure "Install Cydia" IS NOT ticked, and "Just boot tethered right now" IS selected. Then click Next. After a few seconds, you will be able to click Finish. Meanwhile, your iPhone is still working away. After about a minute, the screen will go blank as they keypad locks.
21. Now run blackra1n.exe which you downloaded in Step 7, and click "make it ra1n".
22. Connect to WiFi on your iPhone.
23. Run the blackra1n app which is now on the 2nd page of your iPhone apps. Select Cydia, Rock and sn0w, and then press Install.
24. If your iPhone picks up a network signal, this usually means your phone is now jailbroken and unlocked. If it does not pick up a signal and it is not due to you being in a poor signal area, this means the jailbreak did not work. Start from Step 1 and if you are still having issues, restore to your latest back-up.
Remember, if this method of jailbreaking does not work for you, it is not the end of the world. Don't get worked up about it if it fails; whatever happens, you still have a perfectly good iPod and web browser and a ton of free apps you can download from the App Store!