In short you can't. Apple has a very efficient supply chain so the window where they sell devices that aren't the latest version is very limited.
On occasion a service replacement unit can sit in the "supply" chain a bit longer, so I have seen several people still getting phones from the Genius Bar / AppleCare with iOS 4 loaded. I would expect that to be mostly over as well.
You will likely have to find a seller of a device and you can always ask for the serial number or look for one with AppleCare still active in case you have suspicions of the motivation of the seller.
(and since you or others may wonder)
There really isn't a good way to tell if a phone has been stolen (no police database (and if there were it could always be reported stolen at a later date). Due to privacy concerns you can't get data on prior owners from Apple. You do run the risk of problems if the device you buy ends up being stolen goods. You do run the risk of having to do some work to ensure any return policy is workable if you need to locate the seller if the phone doesn't work as advertised.
Given your problem you might offer to sell a brand new in-the-box phone and once you had a buyer, use your AT&T subsidy to offset the cost of a new unlocked iPhone for your wife. It all depends how valuable your time is and how hot your local market is for current AT&T phones. I would feel a lot more comfortable buying a phone when I could come to the store with you and see the new phone being bought. You could be sure the buyer had the cash in hand and everyone should end up happy.