I spent a LOT of time in the caves, and it seems that shamen can spawn from warriors, gardners, tenders and possibly even vineherds. I found the best way to do it was to kill everything from one end of the caves to the other, rinse, and repeat.
I too needed these for the cultural armor quest. If you're a druid there's a relatively easy...but time consuming....way to do this. Bind outside the cave in a safe spot, then kill the one at the cave entrance when it spawns. I did this periodically over several weeks and got 20 that way. Every 4 or 5 spawns is usually a shaman.
Needed to kill these for my Halfling exalted symbols quest, and of course since everyone just LOVES to help people do quests that don't benefit them at all, I ended up trying to solo them. Pretty difficult for a druid, due to tight spaces in the caves and pats that come at the worst times. To make things more complicated, about half of my gear is OoW or older, and is of course quite outdated. They hit for lower 1k, around 1100-1300ish, and of course cast shaman spells, among which is SoW which seems to add to their innate run speed instead of overwriting it, seeing as how they outran me easily with SoE on. The worst thing is probably their AE root, which I rarely resist with an MR of 327. I managed to solo a handful of them, but the risk was pretty high, especially when I had already used exodus. I would imagine other casters would have similar experiences, though I would bet that higher quality gear (wouldn't take much) would help significantly. Hope this helps!
A darkroot shaman just dropped : Spell: Ahnkaul's Mending Rk. II (SHM 73)
Edit: also dropped later on : - Spell: Armor of Unrelenting Faith Rk. II (PAL 73) - Spell: Dreams of Veldyn Rk. II (ENC 73) - Spell: Winter's Flame Rk. II (DRU 73) - Tome of Echo of Misdirection Rk. II (MNK 73) - Tome of Temple Blow Rk. II (BER 73)
Looks like they can drop every level 73 Rk. II spell or tome.