Your first combo is fine. You could also consider subbing one of the mages for a lock - the extra 13% magic damage from CoE would be handy.

Pally / 4 x Shammy is a proven combo as well, since some totems stack (e.g.: healing stream), and elementals can add extra dps or off tanking, and Pally tanks bring some nice buffs of their own (i.e. BoK).

Cheers,
S.