I really enjoyed leveling a pair of elemental shaman. Reincarnation on both characters means you should never be without a res. You have water walking and water breathing which are major conveniences. Once you get down into your tree and start procing extra spell casts it's a lot of fun watching the non-stop stream of lightning bolts basting into your enemy. No downtime for mana. Killing mobs before they get to you, or at least within 1 hit makes for very fast progression as well.

That being said, it doesn't save you any money on mounts, but at least the low level ones are cheaper now.

As to your question of which race for paly; for practical reasons I would say human for the amazing racials. My personal choice would be Draeneifor stylistic reasons.

Best of luck and have fun.