Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Some stores do carry the 4gb version, not sure about the 128GB ssd though.

Look on the Macbook Air price list.
 
It's worth calling the store ahead, but when I got my Air in Jan '11 my local Apple Store had the 11" 1.6GHz w/4GB RAM & 128GB SSD. So give them a call - you may luck up and still find they keep them in stock.
 
I picked up the 11" ultimate at the Apple Store, I am sure most store will carry it, the only ones I doubt are the small satellite stores, in smaller malls, for those I would call ahead.
 
Most of the larger stores carry the baseline, something in the middle, and then the ultimate version. Smaller stores will usually carry the baseline and ultimate.
 
Every Apple store go to (yes, there are several) in Houston carries the 11" Ultimate. Shouldn't be tough to find in any big city.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.