3x Elemental, can heal together as well as 1x dedicated healer.
You lose a bit of DPS, when you're healing instead of killing things.

But you gain a lot of DPS by having a fourth damage dealer.
Especially if its one of:
a) Boomkin; or
b) Warlock (any spec)
Because that adds +8% spell power, to your other casters... in addition to providing damage.

Boomkin gets you Mark of the Wild, meaning your Pally can go Blessing of Might (since Kings won't stack with this).
You also get Thorns, Innervate for a healer, Battle Rez, the ability to CC animals, root and faerie fire, Solar Beam vs casters, etc...

Warlock gets you a Pet Buff, Healthstones, Summoning (so you can hearth and be summoned back), CC vs Demons/Elementals, better DPS than a boxed boomkin...

Another caster or hunter is an option.
But that means losing the 8% spell damage buff.

Initially...
Have one of the three Elemental Shaman dual-spec.
So you actually have:

Healer Mode:
- Prot Paladin
- Resto Shaman
- 2x Elemental Shaman
- 1x Warlock/Boomkin

Kill Faster Mode:
- Prot Paladin
- 3x Elemental Shaman
- 1x Warlock/Boomkin



The totems are a supplement...

Mana Spring will be up on one of them.
Healing Stream on the others.
One of the Healing Streams will be glyphed for the Resistances.
The Pally will have one extra resist that the Shaman cannot provide, but will generally use Devotion (Armor) or Concentration (All the Casters) Aura.

Your Earth Totem can be whatever.
But you'll have Tremor on round-robin, for use against Fear.

Air Totems can be spell/melee haste.
And Grounding on round-robin, for use vs casters.

Fire Totems can be Searing Totem, when you're not using CC stuff.
And they can be Fire Elementals, anytime you want AoE.