For PvE or Battlegrounds, just about any combination will work.

You have a tank (pally is probably the easiest tank to box with) option and a healer option (druid or priest, both of which rock as a boxing healer).

A Paladin with 4x Shaman is a great option too.
They are incredibly easy to play and have a ton of synergy.
You can run 4x Elemental or 3x Elemental + 1x Resto, its a preference thing really.
The Resto makes harder stuff easier, but once its closer to farm status the Elementals can all dps and heal enough.

Paladin + 4x Shaman will be far easier to macro/hotkey then a mixed team.
This combination can do every heroic.
A 5th shaman is probably a better option for PvP, but you could easily go a Prot/Holy hybrid on the Paladin.
You'd have massive health and decent survivability making you the wrong target to burst if they focused on you.
And provide your team with some heals, especially if you set up mouse broadcasting heals.

As far as the boxing solution, I'll recommend InnerSpace + ISBoxer Toolkit.
For pvp, you'll probably want to have strong mouse broadcasting options for ground target spells.
I've very happy with IS.