Prior to Holy Shield, I'd level the Paladin as Retribution - Big two-hander weapon, Retribution Aura, Seal of Command; I'm not an expert but something like this: http://www.wowarmory.com/talent-calc...31300000000000

Once the paladin can go deep enough in Prot for Holy Shield (Level 40), Weapon + Shield, Stamina/Intellect/Defense gear (drop Int gear once you have Divine Plea + 2/2 Guarded by the Light), switch to: http://www.wowarmory.com/talent-calc...00000000000000

Progress the Paladin towards: http://www.wowarmory.com/talent-calc...00000000000000

For leveling Shaman's I'd go with something like this... Elemental to Thunderstorm being prior to Enhancement (On an all shammy team, possibly instant ghost wolf, before Elemental): http://www.wowarmory.com/talent-calc...00000000000000

Down the road, if you want to respec one of the shammies to a Resto build for heroics (or use the Dual Specialization option), go with something like this: http://www.wowarmory.com/talent-calc...10551122301251



*Edit*

Under Interface options, enable "Click to Move". On the slaves for sure, on the main if it doesn't bother you there.
Under Keybindings, bind something to "Interact With Target".
You'll also need a key for the slaves to assist the main.

With Flametongue weapon, the Shammies can melee for a rather decent amount, even when out of mana.
Once you get Water Shield, this will be the Shield the Shammies should have up at almost all times.

For the druids, I'd assume if they were Feral, one would be Bear form to tank, the others Cat to dps.
You get fairly close and then break follow.
The bear charges in, turns the mob so its back is to the cats.
You click your assist the bear key, and then interact keybind.
The cats "interact" with the mob, by moving to it and starting to melee.
You then click your specials, ideally a key is both bear tanking and cat dps.

Same principle on the shammies. Break follow. Have the Paladin move into melee.
Or at least close enough to pull the mob(s) towards them.
Shammies nuke as the Pally melee's.
Once a shammy is out of mana, they can interact with target, same as the cats.

Between Water Shield and one Mana Spring Totem, mana won't be much of an issue.
3/3 Unrelenting Storm should be a priority to get while levelings, it will help tremendously.
Once you're higher level, you might untrain that for a more useful talent - I kept it on my space girls, but others move the points.
Kings is the blessing of choice for the Shammies.
While you're Ret, probably Blessing of Might, when you go Prot, Blessing of Sanctuary on the pally.
In 3.2, Blessing of Sanctuary will also include the Kings 10% stat boost, so they'd likely all want that.
Blessing of Wisdom does not stack with Mana Spring, and you'll always have at least one shammy doing Mana Spring.