AT&T will
ABSOLUTELY NOT for
ANY reason unlock an iPhone. It does not matter if you paid full price for it, if your contract is up, if you threaten to go to another company, if you're traveling out of the country and your account is in good standing, or if you offer your first born as a sacrifice. They simply WILL. NOT. DO. IT.
In fact, when I was at the AT&T store last Friday getting my 4S, I actually heard one of the employees tell a man that it was "illegal" for AT&T to unlock his iPhone 3GS so that he could take it to Europe with him, but that he was more than welcome to Google "how to unlock an iPhone" and do it himself because it was super easy.
Currently a software unlock is not available for the 4S, but you said you don't want to Jailbreak so that doesn't really matter anyway. Your only option is to buy a factory unlocked on from Apple.