Shaman is one of the classes I've looked at the least. This is gaara's token shaman deck, looks like it was made to counter control warrior
Deck Builder - Hearthstone
As weird as it may sound I think frostwolf warlord is perfect for this deck because with beefy totems you're almost guaranteed 3/4 minions on the board at all times.
A more traditional one probably looks something like this:
Deck Builder - Hearthstone
If flametongue survives a turn you can leeroy+rockbiter+windfury for 22 damage. You can swap unbound elementals and/or a manatide totem for earthen ring farseers if you're seeing a lot of aggro and bgh/tbk for control. But like I said I haven't played shaman in awhile, just going off basically what I see.