Originally Posted by ArkadyF

I am in exactly the same situation.
The tool posted by teamare didn't work. It fails saying ">> Shell could not recover. Exiting."

There is another possibility that might get us an unlocked phone - There is an option to add repositories to the custom IPSW created by PwnageTool.
Unfortunately, adding repo666.ultrasn0w.com and refreshing is not working.
I have a feeling that's because this is an incomplete link which is being filled up by Cydia/Icy. I have no idea what is the full version of it. If we could add ultrasn0w to it we'd be able to unlock it without wifi.

Anyone have any other ideas?

Where can i get this custom IPSW because this other program didnt work.

For a Mac alternative please look at the following thread:
http://www.hackint0sh.org/forum/f159/76588.htm

This tutorial worked for me (iPhone 3G on FW 3.1.2)

YouTube - Unlock Iphone 3g 3.1.2 Firmware Without Wifi (HD)

Used Phoneview on a Mac