Take a look at the map of where Southwest Airlines flies to and you get a feel for 'alternative' cities that should have enough infrastructure for a startup.
In my neck of the woods, albany,ny we were the excitement of the entire area. We were on the front pages of the local paper all the time. Recruiting was easier because people knew who we were and understood we paid less, but had the excitement they were seeking.
We got free legal advice because lawyers wanted to be associated with us. We won local business plan competitions ($100k cash). We got investment from local VC's wanting to build up the area.
We paid $1500 a month in rent, including all utilities, for a mansion on the hudson river (and lived in the 5 bedrooms on the second floor). Our internet (cable modem) was $40 a month and screaming fast because our neighbors probably didn't even have it.
That helped us 'stay alive' long enough to figure out how to make money.