I think Cairne is actually too slow for Shaman. With only 4 damage it usually won't save my life. So I opted only for the most valueable cards for the Shaman combos:
2x Earth Elemental*
2x Faceless
1x Sylvanas
1x Baron Rivendare
1x Kel Thuzad
2x Ancestral Spirit
2x Reincarnation
* Debatable, but by far the best value minion when it comes to dying and reviving.
I think this is the staple for mass duplication. How the rest of the deck should look like is still quite hard to figure out. I've tried a mass taunt version, giants version, deathrattle version, mass AoE removal version and now I'm on a more balanced taunt, draw, removal version.
Doomsayer turn 2 helps quite a bit with delaying, definitely keeping that one golden version in my deck.
2 Loot Hoarder, 1 Manatide and 1 Azure Drake seems to help a lot with filling the curve, putting some sort of threat and still keeping my hand with options.
The giants version seems to lack healing, so I think I have to get Alexstrasza before I try that again. Or maybe having all those necessary cards AND giants AND giants-managing cards (like taunt givers) will cut too much of the deck for me to be able to play anything in the first 4 turns.
Mass removal, including Forked Lightning, was not such a good success. While it usually keeps your board clean, having only 1-3 cards left in your hand starting from turn 5 doesn't allow much room to actually to do the death combos. And with almost every spell giving overload, it often delays or blocks the combos and you just end up being more and more behind with the lower mana availability.
Next time I'll try a Loot Hoarder, Acolyte of Pain with Abusive Sergeant, Flametongue Totem and Dark Iron Dwarf, Azure Drake version. Maybe instead of trying to play catch up removal on the first few turns, 'faking' aggression while drawing cards might be better. As long as you can get to 5+ mana with enough cards and then slam some Earth Elementals and Belchers (or maybe Sunwalker?) the board should swing your way.
Another interesting option would be putting the 2 stealth wolves, Faerie Dragon and Spectral Knight. They all can serve as trade removal, hard to be removed by spells and creates a board, which in a way also works well with Kel Thuzad. Won't have much room for taunts and card draw that way though.
I didn't like Feugen and Stalagg that much with the combos, probably because it doesn't taunt by itself. To use those cards, you probably need a very aggressive opening, but then you'll be hurting for card draw even more, making it even harder to do Reincarnate combos.
Alarm-o-bot is too often a dead card or dead drop unfortunately.
Another concept I want to try is having mass minion summoning along with Cult Master. That way you can open aggressively and still end up with a lot of cards. Will be hard to fit everything in a 30 card limit though.
I haven't tried super early taunt style yet though. Maybe that will work as well: Ancient Watchers, Ancestral Healing, Sunfury Protector, Deathlord and Injured Blademaster to provide some early taunt pressure so you can follow up with card drawers like Manatide Totem and Nat Pagle.
So much to try, so little time!