Why didn't you buy an unlocked version from eBay as they come from countries where they are legally unlocked by Apple?
The only way to unlock the iPhone 3G at the moment is by using a physical any-sim device, it can be purchased from eBay. I have included a listing below which is on eBay UK but will ship worldwide and is relatively cheap. You can check the sellers feedback but I see that he/she has already sold many and most customers are happy with them so it shouldn't be a problem for you.
Ebay Listing
I'm sure in time a software unlock will become available for iPhone 3G as people are working hard on it but until then that is the only solution I am aware of.
Hope this helps!