I'm probably not the best one to answer that, I'm not very good at the whole "eastern" feel myself. A quick search suggests trying harmonic minor, "Hungarian minor", or pentatonic scales.
You can of course try Asian or Arabic tunings, but how easy it is to use those probably depends on what kind of song you're making. The more tonal layers you have the harder it would be to get those tunings to fit. As a page said that I found in my search, "Traditional eastern music is strictly monophonic, which means that it uses only melodies, and it can easily support the inclusion of intensely dissonant microtonal intervals."