Try one of the Middle Eastern box scales, they sound awesome - Opeth and Lamb of God use them to great effect. The Spanish scale sounds awesome for more subtle stuff, and if you're really adventurous, try figuring out a Hindustani raga for guitar!

Here's a Middle Eastern scale that I like to use:

E----5--6-----------------------------------------
A---------4--5--7--8---------------------------
D----------------------5--6-7----carry on up the octave :)
G---------------------------------------------------
B---------------------------------------------------
E---------------------------------------------------

If you're into heavy metal, listen to "I Am I" by Queensryche to get an idea on how to use this scale. The scalar shape can be easily used on any fret on the E string.