Audio-issues has a new post up with a few good ideas for creating interesting mixes. They’re pretty straightforward, and mainly focus on adding new elements (including pads) to a song. Personally I’ve used all those techniques and I’ll continue to do so.
To add to that, I’d also suggest using unconventional processing. For example, in a recent guitar-driven rock project I often used sequenced filter/gate effects to add a modern edge while still retaining the essence of the guitar-based texture.
Another approach is to use some strange experimental effects in the background – create an unconventional ambience. The Sister Freak album I produced in 2010 has a lot of this. We had a lot of fun chipping things up, turning them around and transforming them into bizarre mechanical noises and alien atmospheres. Sometimes it’s not very obvious but it always creates a subtle (or not-so-subtle) sense that the mix is playing by different rules.