Given what Adam said, your best bet to get an officially unlocked iPhone is (probably) through another country. I don't know about the Western hemisphere countries, but in Europe unlocked iPhones can be purchased in UK, France, Italy, and in several other countries. (In some places only through the Apple online store, in others also through brick-and-mortar Apple or non-Apple stores.)
One quite simple way would be this:
- Get an UK "address" from Borderlinx
- Order the phone from Apple Store UK to that address (pay normally with your credit card). Note the FAQ which beautifully explains that it's SIM-free.
- When Borderlinx gets the shipment they charge you for delivery (don't know about US but to Finland it's about $40) and when you've paid, they ship it to you (with UPS or DHL or similar service).
UK is a bit far from you, so consider checking some nearby countries first for similar services. (Or if you have friends/relatives in some country with unlocked iPhones that's of course even better.)
(UK + Borderlinx is a really popular method right now for getting an unlocked iPhone 4 where I live (as testified by e.g. this 45-page forum thread at local Apple fanboy site). Lots of people hate the SIM-locked & expensive Sonera deals we have.)