How to unlock an iPhone 3GS on iOS 6.1.3 jailbroken by Redsn0w?

Am trying to recover from an iOS upgrade (my BIG mistake). I followed the instructions here: http://www.iphonehacks.com/2013/03/jailbreak-ios-6-1-3-using-redsn0w.html, which worked as beautifully as a tethered jailbreak can, but my iPhone remains locked. I don't have any option to go back to the service provider (in Canada) since I'm now living in Tanzania. How can I unlock the phone under these circumstances? If not possible to unlock from this situation, is there another untethered jailbreak/unlock option for an iPhone 3GS on iOS 6.1.3?