I'd aruge that a DK tank is the best to go along with four shaman. If you're running 3 shaman + druid, then a Paladin will be superior because the druid will give you the +13% damage bonus on your targets, plus the moonkin bonus which stacks with the totem of wrath. The Paladin can give you Kings, or whatever other blessing you need. The Paladin will also bring auras (increases healing overall) and a bunch of "oh sh!t" and other useful moves, such as stuns, Sacred shield, and Lay on Hands. Also, now with Exorcism being usable on all targets, Paladin dps has gone up significantly; I personally am clocking 1100-1300ish with my Protection Paladin at level 76 (Sometimes my paladin dps is higher than my druid's dps... I'm still trying to figure that one out myself).

Cheers.