Warlock: Gaara's Voidcaller Warlock
With its unique effect, the Voidcaller is the type of card that enables a deck that simply didn't exist before. The basic shell of spells Gaara uses is much the same as the one found in most Handlocks. From there the deck diverges, running double Doomsayer for additional board clears and as activators for the many Deathrattle cards the deck includes. Void Terror fulfills a similar activator role, as well as giving the deck a smoother curve. To extract maximum value from the Voidcaller Gaara includes two Doomguards and a Dread Infernal. If your opponent can't silence the Voidcaller, then the explosive tempo swing of getting a 'free' Doomguard is devastating. And hilarious.
The lack of Charge means Dread Infernal makes for less explosive turns, but improves the odds that you'll have a Demon for your Void Caller to summon, while still providing a rather useable effect with its Whirlwind-style Battlecry. (You might think about including Illidan Stormrage as a possible alternative.) The deck also employs Jaraxxus as another potential Voidcaller target, bypassing Jaraxxus' effect but providing you with a 3/15 body on the board. As a fallback plan in case you aren't able to knock your opponent out with the demons, there's the trusted Leeroy Jenkins-Power Overwhelming-Faceless Manipulator combo to close the game out.
Play it because… Your opponent will often Mulligan for Zoo or Handlock and be caught off guard by your powerful demon-summoning shenanigans.
Rogue: Naxx Miracle Rogue
Before the arrival of Naxx (and, more specifically, Loatheb), Miracle Rogue was one of the most settled and dominant archetypes in the metagame. There are several different mutations that have appeared since, but the one I find most interesting is the Alexstrasza variant. Prior to Naxx, almost all 9-mana cards were considered too slow to include. Even dedicated Control decks were trying to push their curve lower to compete. Now, with the game slowed down, and with so much more emphasis on board presence, even Miracle Rogue can find room for a 9-mana card.
Since there's less immediate pressure, the deck also employs a single copy of Sprint for additional card draw, since it's harder to guarantee 'going off' with the sort of Gadgetzan Auctioneer turns you had before thanks to the threat of Loatheb. Speaking of him, he also finds a way into this deck, primarily for the mirror match, as does Harrison Jones. Loatheb is the only new Naxx card here, though—everything else is from vanilla Hearthstone. What's interesting is to see how much an established deck like Miracle Rogue has had to adapt to the shift in the metagame.
Play it because… Even though it's not quite as powerful as before, casting tons of spells and drawing your entire deck hasn't got any less satisfying.
Shaman: Kibler's Midrange Shaman
At first glance it seems like the Shaman class hasn't changed much. This build, created by Magic:The Gathering Hall of Famer Brian Kibler really takes the board control mentality to heart. The burst potential of Al'Akir has been completely cut—instead, the deck includes a pair of Sludge Belchers. The Fire Elementals are also gone, replaced by two value-packed 6-Mana Legendaries in Cairne and Sylvanas. The curve overall is lower and the deck is far more aggressive. This isn't the sort of Shaman deck where you want to be playing a totem on turn two. In fact, it can actually have some explosive starts with Undertaker curving out into Nerubian Egg and Harvest Golem.
This sort of build really highlights what the climate in Hearthstone is like right now. Secure an early lead, snowball it into a win by the midgame, and have a back up plan at the top of your curve in case something goes wrong. Between its extremely efficient removal spells, and the new Naxx minions, Shaman is in much the same position as Priest now.
Play it because… You like fast wins, but not having to rely on them. This is a solid, flexible deck. Plus killing Twilight Drakes with an Earthshock and Hexing Savannah Highmane never gets old.
Next page: Hunter, Paladin & Warrior.
