I dont do arenas, but I have had really nice fun with tank pala and 4 x resto chamans and 5x resto shamans and no paladin.

For casters... you can just drop the grounding totems and lb/cl them to death. It's not that good looking like ZOMG LVB spam, but it's effective.
For melee, just drop magma totems or fire elementals and chain heal. Throw ocassional flame shocks just for the fun of it. Let the magma totems do your work. Have earthliving (lifegiving or whatever it's called) weapon up instead of flametongue and you will see very frequently your entire group with Hot x 5 + the individual riptide. If your group is spacegoat shamans then throw also gift of the naaru racial and you become a healing powerhouse.

That's the only way I have managed to get first on damage, healing, killing blows and honorable kills at the same time for the entire BG (horde and alliance sides).

Also magma totem has a very nice utility against skillcloack rogues, it burns them to death. There is nothing better to see a rogue pop lolcloack, realize that he will die anyways to the totems and try to vanish just to reappear dead one second later.

Not sure how this may work in arenas because people are much more focused there than in BGs, but you could try if you have healing offspec on your shamans.As much you may lose some matches.