That is your only option. Only the carrier that the phone is locked to can unlock. IF AT&T won't do it, then you can't unlock it.
Any illegal such as hacking or jailbraking will void your warranty with apple. And even brick your phone.
For about $20 you can buy an unlocked GSM phone anywhere in the world, then get a pay-as-you-go SIM for it. Use your iPhone only on WiFi. If you want to be reached from the US get a free Google Voice number and have it forward to your $20 phone for about 2¢/minute.