Hearthpwn

After much testing and many deck iterations, I've finally found a version I'm happy with. This version of the deck took me from ~2500 legend to ~1500 with a 70% winrate.

As for how the deck performs, it's generally pretty good. Ignite mage is by far the worst matchup (flamewaker variant can be beaten semi-consistently), pirate warrior is a roughly even matchup, shudderwock shaman is a favourable matchup, and c'thun druid gets absolutely stomped.

Deck is pretty self explanatory in how it plays, but I'll add a guide if this post gets 3 likes.

------

3 likes has been reached, so it's time for a quick guide.

The deck is fairly simple. Try get Vanndar up as soon as possible, then swamp the board with big minions which most classes will struggle to remove. The secrets are there to help with the early game, and Sword of the Fallen can remove some small minions, but most importantly it thins the deck so you can draw into your stronger cards. There are some anti-aggro tools (namely consecration and barricade) to help with staying alive in the early game. Now, onto specific matchups.

Mage:
Without a doubt the most annoying and worst matchup. 99% of mages will be playing OTK decks (with either ignite or flamewaker). Against Ignite Mage, there isn't much that can be done since they will kill you on turn 8.
Against the Flamewaker variant, the win condition is fairly simple. Build a giant board that will soak most of the damage. As for how to do this, Vanndar and Barnes are fairly vital. Vanndar for the cost reduction of the other big minions in the deck, and Barnes because there's several good pulls, but the main ones you want are The Lich King and Y'Shaarj. Lich King can generate Anti-Magic Shell or Army of the Dead which will make a board that they likely cannot deal with. Y'Shaarj will pull some large minions from the deck, which makes pressuring the mage much easier. Try and land Oh My Yogg! on either card draw or Incanter's Flow, so save it until ~turn 3, or even turn 5.

Warrior:
It's always Pirate Warrior, and you want to play for tempo otherwise you'll fall behind and lose. In Mulligan, you want to look for Sword of the Fallen, Consecration, Vanndar, Barnes and even Cavalry Horn. Lokholar is also a decent keep, since by turn 5 you'll already be under 15 health.
Whilst you need tempo, you need to balance it with board clear. If you have a choice between playing Vanndar or Consecration on turn 4 and the pirate warrior has a decently large board, always go for the Consecration. 9/10 times the damage you prevent from clearing the board will be more important than potentially drawing a minion with reduced cost. That being said, Vanndar can be a game changer, especially if you end up getting a Brasswing, so if you have a relatively safe opportunity to play him, go for it.
Once again, Barnes can become the MVP of this matchup. Scrapyard Colossus will wall the pirate warrior for a bit, Brasswing will clear the board and heal you, Templar Captain can potentially remove a minion and summon a 5/5 taunt. You get the idea. Normally the games are won after the warrior gets The Juggernaut, so don't sweat if you're seemingly behind.

Shaman:
Most of the time it'll be a Shudderwock deck, so you need to deal with them before Shudderwock properly goes off. Once again, you want to mulligan for cards like Vanndar, Barnes, Cavalry Horn, anything that can let you cheat mana. That being said, it is perfectly correct to keep 1 large minion in your hand during the early game. A decent amount of the time, the Shaman will play Dirty Rat in the early game, thinking that you're a handbuff paladin. If they pull a big minion from your hand, the game is already won 90% of the time.
Once again, Sword of the Fallen is great for deck thinning, and they'll try play around the secrets. Oh My Yogg! doesn't have a bag target, as it can prevent Ice Fishing from drawing Firemancer Flurgl, and stop Windchill from freezing one of your minions and drawing a card for the shaman.
Equality and Consecration, as well as weapons are nice in the matchup since you want to keep Shaman off the board for the most part. The most important thing about this is specifically to kill Firemancer Flurgl after its played, and if possible to kill Shudderwock (if it was unable to duplicate itself and return to hand).

Druid:
Most of the time it'll be a C'Thun druid, and it's a pretty easy matchup. If they use Biology Project, it helps us play our cards sooner, and get Vanndar on the field before we draw too many of the minions. These Druids have almost 0 board presence so it's extremely easy to overwhelm them with big minions. Whilst they do have poison seeds and spreading plague, those only buy the druid a turn in most cases.
For the Mulligan, you want the usual cards. Sword of the Fallen, Vanndar, Barnes, Cavalry Horn and strangely enough, Consecration. Consecration is there for 2 reasons. If you encounter an aggro Druid, you'll need it, but against C'Thun druid it's there as an answer to Glowfly Swarm.
You want to avoid over-filling the board (especially with your hero power) as it makes dealing with Spreading Plague and the aftermath of Poison Seeds much harder. Other than that, there's not much to be said as this matchup hasn't been very challenging yet.

That's it for the main matchups. Most of the matchups play in the same way but with slight variations to mulligan. Only other noteworthy matchups I can think off are Quest Hunter, which has the same game plan but you want healing (Vitality Surge and Ragnaros Lightlord). The other one is Big Rogue and all I can say is good luck, you'll need it ;)