It's been available in the UK store since day one and that's probably true for most other countries. The US was exceptional in the sense that you couldn't directly buy an unlocked iPhone from Apple.
Canada has has an unlocked version since the iPhone 4 release and the coverage on four carriers. If I hadn't had a $0 upgrade to the 4, I would have bought unlocked just for travelling.
No doubt it was part of their deal with AT&T. U.S. telcoms (especially AT&T) are big bullies. Apple needed to play ball when they were first getting started.
Now of course, they don't need AT&T, so they're dropping all the restrictions as soon as they're legally able to.
UK Store: http://store.apple.com/uk/browse/home/shop_iphone/family/iph...