If I go for a complete overhaul, I get my butt into the battlegrounds. Standing in front of the tackling dummy is fine to check for basics. But I have found that unless there is some pressure, then it just doesn't count. Battlegrounds give me a little pressure, but if I mess up, I am not wiping the raid.

Rebind a few at a time. In my experience it's easier to adjust to a few things at a time than throw a huge revamp in your face. Perhaps start with your primary nukes and one or two less used spells.

Or, if you aren't going to be using some former keybinds, double-bind the spell to both keys until you've trained yourself to use the new one. That way, in a panic or a clutch, you won't be in trouble if you go back to your habit of hitting the old key only to remember too late that you've rebound say, iceblock from 5 to G (example of course). On my priest I actually have Guardian Spirit permanently bound to two different keys. Paranoia I think.

Lastly, regardless of whether you ease into new binds or just throw everything out the window, practice using your new buttons in low stress situations - heroics or training dummies. Teach yourself the new binds again. That way you're not fresh in a raid or bg or arena fumbling for your keys instead of dpsing, tanking, or healing.

Stand in front of a target dummy and practise with your new bindings. If you want a randomly moving target practise on the active Tournament Champions outside CC.

there is also an addon called HelpMeKeybind that can be found on curse or wowui.

it helps a lot for learning new keybinds and getting your reaction speed up on your current ones, in a minigame fashion

First, change it all at once or don't, and don't look back until you've shown that your new bindings are worse. I haven't yet had to do a keybinding overhaul, but I have moved important things around.

What I tend to try to do is pug an easy Heroic -- typically UK or Nexus. Something that it's rather hard to foul up, and try it there. Make sure to use ALL the keybound abilities at some point, just to help teach you where the buttons are. Make sure to have visible ActionBars with the keybinding hovering over the button (if it's for spells). Otherwise, it -will- come, and it, at least for me, doesn't take too long. Again, pug runs (or guild runs where you're letting them know what's up) are great for this.

Since you are taking the plunge, I'd also suggest messing with an action bar mod like Bartender4 or Dominoes.

When I decided to revamp ALL my characters to standardized as much as possible keybindings for healing/AoE/racials/anti-fear actions, I modified my keybindings to match my physical keyboard layout. I actually use my numpad keys as well as my normal number keys because I can only use so many shift/ctrl/alt modifiers before my hands start to cramp up. So I made a action bar 3 wide and 4 tall to match the numpad. That way I don't even have to remap in my mind which action bar button corresponds to which physical button.

Of course using the numpad for actions is not recommended if you circle-strafe or jump shot a lot as you have to take your hand off the mouse, but it works well enough for me .

I'll also suggest trying out using your arrow keys to keybind to auras/stances/forms (with modifiers if you need more than 4) to free up some key space.

Edit: If you're going to downrank an answer at least say why. Hopefully its something better than "that idea doesn't work for me".