I've done him with:

Prot Pali (tank)
Arc Mage
Aff Lock -or- Bal Druid
Ele Shaman
Holy Priest (healer)

The priest is was makes this a cakewalk for me, so my strategy obviously won't work the same for other healers, but a resto druid should be close with the group HoTs. I just spread out in the first circular platform before him, about 10 yards which is enough to reduce the water elemental surge (charge) damage to a minimum, then pull him to the center. Drop a nature resist totem (very important). I just use Prayer of Healing (big group heal) every once in a while during the water phases, and just big heals directly on the tank during the golem phases. Just need to taunt at the start of each phase since there are aggro drops. I don't move except on the tank, since the priest has always been able to keep up with the healing with the totem down.

My shaman will also be alternated with hunter later on (currently level 62), which still provides me with a nature resist aspect for things like this.

Gift of the Wild provides at least some nature resist to the group, but obviously not as much as the totem (like 54-75 resist compared to 120 resist).