Hi,
The following solution worked for me. (Actually it was a long process that took about 48 hours to complete; but I'm describing the last 2 hours, where lies the solution).
Step 1: Restore your iphone 3gs to 6.1.3 using iTunes. (You can either download the ipsw from elsehwere and shift restore or do the simple restore from itunes. In case you are struck with some errors, either repeat the restore process a few times; and it that is not working download iReb and enter DFU mode and then try restore from itunes again).
Step 2: Download Redsnow 9.15b3 and also iOS 6.0 for 3gs (available in lot of sites, google and find out).
Step 3: Right click redsnow exe file, choose windows xp sp3 compbatibility mode, and then run as administrator
Step 4: In RS, first click extras and click select IPSW, and chose iOS 6.0 that you downloaded in step 2. (even if you are trying to work on iOS 6.1.3). (You'll be asked whether you're on old bootroom or new bootroom, choose accordingly, if you dont know install forecast from ultrasnow and find out which bootroom you're in)
Step 5: Click back, and then choose jailbreak, and select install cydia and upgrade to ipad baseband and click next. (ipad baseband doesnt work for newer 3gs after a certain version. It will prompt you, ensure that your 3gs is compatible and will work with ipad baseband).
Step 6: Follow redsnow DFU instructions starting from switching off your iphone religiously as mentioned in the instructions. (Don't interpret it yourselves, just do as instructed).
Step 7: RS will fetch bb, the device will jailbreak and flash bb etc. and this will take approx. 10-15 minutes. (Relax. It is working, although there is no sign of it in the initial phase where RS is fetching files). Your device will be rebooted, but there would be no cydia. Dont panic, actually you dont even need to open your device (But if you are curious to know what is inside, you can go to settings and find that you're running ios 6.1.3 on bb 6.15)
Step 8: What you should actually do is that go back in RS, then click extras, then just boot (if you had quit RS before, ensure that you select IPSW 6.0 from where you downloaded early - Step 4). Once you do just boot, follow DFU instructions and wait for RS to finish. Now your device will have cydia as well. But wait, few more steps remain. (You can actually skip step 9 and go to step 10 directly for untethering and unlocking, but step 9 is suggested as it is the best format your iphone 3gs can currently have. If you skip step 9 your device will still work, but is susceptible to 1. erroneous GPS, 2. Failing network. 3. Bad battery life).
Step 9: Come back to RS, now select IPSW (as in step 4), and then go to jailbreak, click only downgrade baseband option. Follow DFU instructions again. Once done, you'll have iOS 6.1.3 with bb 5.13.04 (you can see in settings, general, about). But you're not yet unlocked yet (i.e. it still shows no service).
Step 10: Before you unlock, first load cydia and and update it (you can do it by going to changes, then refresh, then confirm; finally reboot). Now, first search for p0sixspwn and install (so that you're in untethered jailbreak; until this step you had tethered JB).
Step 11. Now, go to Cydia again and search and install ultrasn0w. Respring the device (I suggest you reboot manually as well, slide to power off and then switch on; although this is not mandatory). Insert a SIM Card of your choice. The status will be searching for a while (from approx. 1-5 minutes), but dont panic. You'll be delighted to find a 3GS with full functionality in a while
Cheers!
Salman
Facebook
Twitter
Instagram