You need a tank, and a paladin is the best 5-man tank available, for many reasons. As for the rest of your group, it's hard to beat four shamans. They have both single-target and AoE DPS. They have great synergy and utility via totems. Tremor and grounding totems absolutely trivialize many fights. They can heal extremely well even in DPS spec. They wear mail. They also work particularly well with pally tanks, thanks to Mana Tide and Totem of Wrath.