Pally+4xShamans is popular for a reason.

It's a good PvE team that can be played as Tank+Healer+3xDPS or as Tank+4xDPS if you're comfortable with healing streams and the occasional odd 4xLHW topping off the tank. It's also a good PvP team with the 4xShaman part. Works well in arenas and works well in BGs.

I personally wouldn't recommend a melee team as someone's first 4-5x multiboxing experience.