AT&T retail stores can get them anytime. They get phone shipments daily but it doesn't necessarily mean that the shipment will include iPhones. If it does, they just put them out on the floor, your best bet, if you want to go to an AT&T store is to call around when your store gets a shipment.
Another alternative is to order online through AT&T, they say they are shipping the phones in about 7 business days.
The route I would go is if you are close enough to an Apple Store, call them and have them put you on their waiting list. Once the phone comes into the store, it will be reserved for you for 24 hours. That is how I got my phone and the wait for me wasn't bad, about 5 days but I think the average is about 7 days.