1. make sure WF and water sheild is up.

2. GW up to him and stormstrike/flame shock/earth shock like crazy (frost if he runs)

now you should be able to do more dmg then the pally, hes just gonna take a long time to kill, and you want the first move on him, or else it will stun and hurt)

3. When they reach low health they bubble, take this time to heal, re-buff water sheild if needed (should be doing this anyway through fight)and if you have to pop shamanistic rage.

4. the fight will pretty much start again, rinse and repeat until all he has is CD.

note: if you have to drop totems, id go for SoE, searing (magma if you got the mana), GoA and mana spring. if he hits hard replace SoE with stoneskin. :D

In my opinion Elemental Shamans has an easier time in killing pally due to pallys got hardly any range skills, kite (use frost shock and earthbind totem to make kiting easier XD) and spam lightning bolt lol but anyways if you have Elemental mastery and Natures Swiftness, cast both and do an instant Chain Lightning and hope for Lightning Overlord to proc XD

But Enhancment and Resotration can take down pallys so I'm not argueing which is the best :P