I've heard good reports of the Arabic school in Manah in Oman. It is a small town and there will be very few English speakers in the area.
Here's a link with some details and some feedback from attendees. A bit of searching should get you more info.
http://www.angloomanisociety.com/ara...guage-scheme-0