Is it possible to unlock iOS 6.1.3 already?
I have 3Gs with New Bootrom but manufactured before 2011. I had accidently updated iPhone from iTunes to 6.1.3. That upgraded my baseband to 05.16.08 and left me with a locked phone.

This is what I did.  You can do the same even if you have old Bootrom (that is in fact a boon since you’ll get untethered jailbreak of 6.1.3). But if your phone in manufactured in 2011 (exact date please Google it), then DONOT ATTEMPT THIS.


Thumb Rule: Make sure your internet connectivity is present throughout. Make sure of the versions of software mentioned. Make Sure you have shsh blobs of 6.1.3 present (in case you want to go to 6.1.3 in step6). Run all tools as “run as administrator” on windows.
Download iOS 4.1. Download Latest TinyUmbrella. Download latest iREB. Put your iPhone in Pwned DFU mode via iREB (Dark screen with no logo). Start TinyUmbrella TSS Server and use iTunes 11 to flash stock 4.1 onto iPhone (hold shift key while selecting restore from iTunes and select 4.1 iOS). Now your Phone is on iOS 4.1 and Baseband 05.16.08, since baseband cannot downgrade via iTunes.
Jailbreak using Redsn0w V0.9.14 b2– Select option Install Cydia and Install iPad Baseband. Now your Phone is on iOS 4.1 and Baseband 6.15.00. (May require couple of retries. If putting DFU mode from Cydia doesn’t work, try putting it in DFU mode through iREB)
Once Jailbroken, run Redsn0w0.9.15b1 – select ios4.1 from extras and deselect Install Cydia and select downgrade from iPad baseband. Now your Phone is on iOS 4.1 and Baseband 5.13.04. (May require couple of retries. If putting DFU mode from Cydia doesn’t work, try putting it in DFU mode through iREB)
Now you have a working iPhone 3gs on iOS 4.1 untethered and you can unlock it from Ultrasn0w. Proceed below only if you are willing to risk a tethered jailbreak for 6.1.3 
Download iOS 6.0.0 and 6.1.3 for 3gs. Download sn0wbreeze v2.9.14. 
Start TinyUmbrella TSS server. Prepare Custom ipsw through Sn0wbreeze with option iFaith. When it asks for 6.1.3 appticket, pass on shsh blobs for 6.1.3 (This mode will preserve baseband too, so don’t worry). Sn0wbreeze will prepare the ROM (takes some time). At the end of it, it asks you to put your phone in DFU. Don’t use that. Close the Sn0wbreeze and use latest iREB to put phone in Pwned DFU mode.
Start iTunes. Use shift restore and select ipsw built by Sn0wbreeze. When restore is complete and it reboots, press home+power key to force shutdown and reboot using the iBooty tool created by Sn0wbreeze in Step 7 which is now placed on your desktop.
Now run Redsn0w0.9.15b1, select ipsw in extra as 6.0.0 (not 6.1.3!!). Click on jailbreak and install Cydia option. (May require couple of retries. If putting DFU mode from Cydia doesn’t work, try putting it in DFU mode through iREB). Whenever the phone is booted, don’t boot from Redsn0w’s ‘just boot’ option. Always use iBooty. If it starts booting in between, force shutdown from home+power and start with iBooty.
Now you should have a 3Gs on iOS 6.1.3, which is Jailbroken (tethered in case of New Bootrom) and fully unlockable through Ultras0W at baseband 5.13.04. You’ll have to use iBooty every time you iPhone restarts.