I can get (non UL-listed) Chinese-made, propane-fired outdoor tankless heaters for $85 each out here. They are small and you need one outside each bathroom or fixture for them to work right, but a few friends who have them swear by them. (maybe I should open an eBay store selling them to you suckers.... )
I'd personally rather opt for a UL-listed appliance, and an electric one just to save the trouble of buying gas all the time. I already have a gas range that's fed with a 90lb tank, and it's such a pain to get it refilled, and it always runs out on a Friday afternoon, leaving us stuck without an oven until Monday. But then again, when our power was out twice a day for 3-4 hours at a time last year, a gas-fired water heater would have been a nice alternative....