I know very little about Al-Qadim, but I think themes would work really well. Looking at the Wikipedia entry for Al-Qadim, most of the classes (or I guess they were probably kits) either map really well to an existing 4e class, or could map well with the help of a theme. For example, the Holy Slayer sounds a lot like an avenger, while the elemental mage could be just a theme, some feats, and focused power selection for a wizard, sorcerer, or even a warlock.
The sha'ir is the only one that looks like it might require a bit more work. I could see sha'irs as (mechanically) shamans, summoning wizards, or even warlocks, depending on how you tweak it.