It’s happening, The iPhone Dev Team has just Released Ultrasn0w 0.93 to Unlock the Final version of iOS 4 on both 04.26.08 (on 3.1.3) and 05.13.04 (on 4.0) Basebands, This Unlock for iPhone 3G and 3GS. Step by Step guide to Unlock your iPhone 3GS on Baseband 05.13.04 posted below..
Steps:
Step 1: You should have a Jailbroken iPhone, you can use Step by Step guide to Jailbreak iPhone 3GS / 3G posted here.
Step 2: Navigate to Cydia Source by Going to Cydia –> Manage –> Sources.
Step 2: Touch on “Edit” and then on “Add”. Type “http://repo666.ultrasn0w.com” then hit “Add Source“. Ultrasn0w will be added to your Cydia Source lists.
Step 3: After you install Ultrasn0w in your Cydia sources list, Search for “ultrasn0w 0.93” and install this app, and it will automatically unlock your iPhone 3GS.
Update 1: It’s confirmed to work on all basebands (04.26.08, 05.11.07, 05.12.01 and 5.13.04) More details Here.