I entertained the idea to spend some time in Dubai as well, considering I have to change planes there anyway.
I talked to a friend last week who lived for several years in Al Ain, a city in the UAE on the Omanian border.
It seems the UAE are okay for travelling by yourself, but a city like Al Ain with a population of over 370,000 and a possible gateway into Oman has no cheap places to stay. Only 5 Star hotels, way over our budget.
Getting over into Oman is possible but takes some time and you need a four wheel drive and a local guide to cross the desert. She said the desert is dangerous unless you travel in a group.
There are no trains in the area, but some long distance buses. You can go from Muscat in Oman to Dubai (5h) and Abu Dhabi (6h). The Lonely Planet for the Arabic Peninsula also mentions a bus from Muscat to Mukhalla in Yemen (6h) but I don't know whether that is still running considering the situation in Yemen right now. (I was in Eastern Turkey a few weeks ago and all buses to Damascus had been cancelled.)
Overall I get the idea, that the infrastructure for independent budget travelers does not exist in the area.