This is purely for leveling purposes? What are your plans with the characters once they ding 70?

4x shamans is one of the most fun combo's in PvP at 70, no doubt about that. 4x druids offer a lot of diversity, whilest they might nog shine as much in pvp, they have the potential to shine in pve. 4x shaman and a mage could do heroics as well and such so, both could work in pve. Just that 4x druids would allow you to last much longer in fights, do to having a proper tank. Feral+2x boomkin+resto seems like a well fun combo with a mage as a 5th.

The druid can res but on a cd, however, if you have 4 druids, there shouldn't be much of a problem. And if its a wipe, can always just run back. I wouldn't take this factor too much into account with rolling a character set up.

4x paladins, mmh, I wouldn't do that personally. You've little to nothing to do in pvp as a box, and for pvp, you would only have one healer max, and then three melee, likely one prot and two retri. And 3 melee is just a lot of annoyences. It's more of a challenge as well, to do it, so it might work for you. But I wouldn't recommend it.

I play four shaman, I love them to death. My choice, what is yours?