In reply to Kassius:
Food and water are going to be tricky, but if you are prepared to carry a short distance to the camp you should be OK. I have worked in Ras al Khaimah, taking groups into the mountain wadis, and i think this would be the easiest to get to from Dubai.
Dubai airport- metro to Union Square- bus to Ras al Khaimah. From bus station, taxi to mouthof one of the wadis via a supermarket. Ifyou want a feeling of remoteness, but accessible, I would recommend wadi Naqqab, which is the next big wadi S of Wadi Bih, heading east into the mountains. A taxi will take you to the end of the tarmac, a dirt road continues in for a few km into increasingly wild, narrow gorge. There are settlements for the first few km, with the chance of a lift and probably very generous offers of hospitality.
You can find plenty of places to camp, lots of ancient trails, and either retrace your steps or head S to Tawiyan for a real adventure. Alternatively, bus to Tawiyan (on way to Dibba), once there, follow new road and drop into the gorge (good cragging here) and walk along this- not as good as Naqqab, but interesting.
People are super friendly, and will be fascinated by you wanting to backpack. Have fun, the weather in January (assuming no rain) will be perfect.