Typically I'd probably go fire spec for PVE levelling. However, if your mage is lead, frost might actually be better. Slow down those mobs and knock them down before they even get to you. Especially since DPS won't be an issue with 4 shaman.

Also, having the 4 shaman as slaves really won't be any different than having 3 shaman and 1 mage as slaves. It may seem that since they are all the same it works better, but IMO it really it makes no difference. You press 1 button and DPS. What does it matter if you cast lightning bolt or fireball?? It would only matter if it were melee versus ranged DPS IMO. Although, I'd still make the mage lead for other reasons unless you want to make one of your shaman enhancement.