Using WASD where AD are strafing, E and Q are other binds. But what gave me more new good binds was to start using modifiers with WASD, however I find the CTRL button extremely inconvenient for my hands. Thus installed sharpkeys, and bound caps lock to control which I find to be amazing: have to move my pinky just a little bit up and down to toggle a whole new set of keybinds.

And then the biggest thing: I bound my naga to numpad, and in combination with a hotkey script, I can use both alt/shift and ctrl + numpad. That is another 48 hotkeys that are unlocked.

A typical naga macro for me looks like (this one bound to naga 1)

/tar [nomod] arena1
/focus [mod:alt] arena1
/stopcasting [mod:shift]
/cast [mod:shift, @arena1] counterspell
/stopcasting [mod:ctrl]
/cast [mod:ctrl, @arena1] sheep

Same macro on naga 2, but then arena1 is replaced by arena2, etc
And this obviously can be extended to make them use in pve as well.
When boxing I heal with target heals: naga1 targets party1, naga2 targets party2, etc ...

As far as my experience with swapping out binds it goes faster than you would expect:
at the start of MoP I swapped my Azerty keyboard (french layout) for a Qwerty keyboard, you can imagine how much of a frustration that creates during the first days as pretty much every character is on a different location. 1 week into it I'd still have problems with a few keys like ' or %, but for 99% of my typing it was no problem at all. Now I even use qwerty and azerty keyboards in the mix, since my laptop is still azerty.

TLDR: swapping to something you got so used to goes faster than you might think, but you have to stick it through.