Hi everyone, wickedBBQ EU Legend player here.

Proof:

Quick update:
I hit legend in the January season as well, with some small changes in the deck.
Proof:

As I promised, I'm going to write a full guide about the deck. Let's talk about card choices first.

• Zombie Chow - We need him early game to fend the aggro off, he really shines against hunter, he usually trades 2 for 1 in this matchup.
• Knife Juggler - Synergy with muster, equality+muster, Haunted Creeper. Again I found one copy of it enough.
• Shielded Minibot - An amazing card, that divine shield helps a lot against early aggression.
• Ironbeak Owl- We need one copy of it, silence is a must nowadays. I prefer owl over Spellbreaker, because it costs only 2 mana, and Spellbreaker has that 4/3 body which is pretty bad, it just dies to a 2 drop.
• Equality - Combos great with Consecration, but can be used without it as well to make good trades. Wins you games late game, especially against Handlock and Control Warrior.
• Muster for Battle - Another amazing card Paladin got with GvG. It creates tokens, which can be combo'd with Juggler, Quartermaster, creates board presence, and also gives you a Light's Justice which I found to be pretty useful, good against aggro decks in the early game, and it helps you ping off divine shields etc.
• Aldor Peacekeeper - Do I have to talk about this one? :) Best used on Big threats like Giants etc., but when facing Aggro decks, you can Aldor lesser threats as well.
• Big Game Hunter - Amazing against Handlock and Control Warrior, I'd say its a must in this meta, where everyone runs Dr. Boom. Against Aggro decks you can drop this on turn 3, but beware, some Zoo decks run Sea Giants now (Xixo version), so you might wanna keep it, but if you're feeling pressured and you don't have any other play, just drop him on the board.
• Consecration - Paladin's good 'ol board clear, combo's with equality.
• Truesilver Champion - A must in every Paladin deck, I think I don't have to talk about this one.
• Piloted Shredder - A very good mid game card, helps you make good trades, 70% of the time you'll get a good card, and sometimes Millhouse pops up :)
• Harrison Jones - Another obvious card. He helps a lot against classes that have weapons, and after GvG hit a lot of new weapons appeared.
• Sludge Belcher - An extremely sticky minion, helps a lot against Aggro decks.
• Quartermaster - Another amazing addition with the release of GvG, this guy single-handedly wins you games. Obvious synergy with your hero power, and Muster for Battle. The thing is that you shouldn't be greedy with it. Dropping him on just one token is fine, 2+ are great.
• Dr. Boom- Creates board presence, those Boom Bots often helps you trade in you favor, it is an amazing card.
• Tirion Fordring - One of the best legendaries in the game, if the opponent does not have an immediate answer for it, he usually just wins the game. He also has taunt, which is very important against Aggro Decks. If silenced, you'll still have a 6/6 body.
• Lay on Hands - Our card draw/heal mechanism.

Cards I've tried and removed:

• Guardian of Kings- Works great in Control Paladin, not so much in Midrange. He is too slow for this deck, he costs too much, you'll often find him stuck in your hand just to drop him at full health.
• Cairne Bloodhoof - I found him too slow, the opponent often just ignored him/silenced him.

Substitutions:

When facing a lot of Aggro decks, you can remove the Haunted Creeper and 1 Zombie Chow, and put two Annoy-o-Trons in the deck. They are doing an excellent job stopping early aggression.

Mulligan Strategy:

Handlock:Equality, Ironbeak Owl, Aldor Peacekeeper, Big Game Hunter

Zoo, Hunter, Paladin, Shaman, Aggro Mech Mage/Druid: Zombie Chow, Shielded Minibot, Knife Juggler, Muster for Battle

You can also keep consecration in these matchups, IF you are going second, and you have the above mentioned early game drops.

Control Warrior: Shielded Minibot, Big Game Hunter, Harrison Jones, Piloted Shredder and Truesilver Champion IF going second

Ramp Druid: Aldor Peacekeeper, Zombie Chow, Shielded Minibot, Knife Juggler

Priest: Piloted Shredder, Shielded Minibot, Knife Juggler, Aldor Peacekeeper,Truesilver Champion

Matchups

 

Handlock: 70/30

Aldor their turn 4 Giant, Silence their Drake, if you do not have silence in your hand Aldoring a Drake is fine. Try to bait out their removals with buffed tokens and smaller minions, their silence with Shredders. You can be aggressive in this matchup, IF you have equality you can pressure the Warlock to have an answer, if you don't have it, stop around 15 hp, because if you get him to 10 or lower, he'll drop those taunted moltens, shadowflame one to clear the board ( or shadowflame their other minion), and you'll find yourself in a bad position soon.

Control Warrior: 70/30

Shielded Minibots are amazing against those early fiery war axes, that divine shields help a lot. You must be aggressive in this matchup, usually the warrior will run out of answers, because he has to deal with the buffed tokens and shredders, and will have no answer for you late game threats. Try to bait Brawl out as soon as you can, so you can pressure him again. Warriors sadly run 1 or sometimes 2 copies of Whirlwind nowadays, so dropping Muster early game is a bit risky, and the Death Bite's Deathrattle hurts as well. You should have the upper hand when your deck contains 10-15 cards. After the Warrior runs out of steam, use Lay on Hands, and seal the deal.

Zoo: 55/45

The key to victory is to be able to control the board, and to keep it clean afterwards. Zoo has no board clear, so you can drop as many minions as you want; try to make good trades, the best silence target is Nerubian Egg, but using the Owl on other targets is fine as well. Dropping those Belchers and Tirion helps in this matchup tremendously, often when you drop Tirion you' ll just win the game.

Hunter: 50/50

You must be the aggressor in this matchup, as interestingly it sounds, because if you try to be passive, the Hunter will just hero power you down, and those Skill Commands will land in your face in no time. Sometimes they will get double undertaker opening, and snowball the game quickly, but that's not often the case. Try to stay out of Kill Command range, healing yourself with Lay on Hands is very important; Tirion and those Belchers hurts the Hunter as well, they often have to use their Bow/Kill Command to deal with them, which is good for us, because it's not going to our face. The 1/1 tokens are doing an excellent job by eating a Freezing Trap.

Shaman: 60/40

The same strategy with Zoo, except the overextending part, because Shamans have Lighting Storm, which hurts you. Try to bait their Silence out on Shredders, pressure him. Consecration helps you a lot in this matchups, their tokens die immediately; the best target to Aldor is usually Fire Elemental. Use BGH on Neptulon, as often this is the only target they'll have in their deck.

Priest: 30/70

Our worst matchup, Priests can do a lot of nasty things that hurts you. The good news is that there are only a few of them in the ladder nowadays. Try to play around Shadow Madness, if turn 6 comes, assume that they have Cabal in their hand; the only safe time to drop Tirion down is on turn 8, because later he'll get Mind Control'd, which often results in losing the game. Do NOT overextended, because the Auchenai Soulpriest+Circle combo will often clean your whole board; the best Aldor target will usually be their Injured Blademaster.

Aggro Mech Mage/Druid: 55/45

The strategy is the same as we do in the case of Hunters, we must be the Aggressive ones. Try to keep the board clean, make favorable trades. Always kill Mechwarper, because its ability will let the enemy snowball the game. Snowchugger must be dealt with as well, as it will keep you frozen the whole game, denying the use of weapons, which will hurt you a lot. In the case of Mech Mages, try to stay above 15 hp ( double fireball, frostbolts). Mech Druid is similar, try to stay above 14 hp (Force of the Nature+Savage Roar combo), and try to bait their Keeper to silence your Shredders, often they'll find themselves with no answer to Tirion.

Paladin: 50/50

Try to use your equality+consecration combo efficiently, if you know you're in a Mirror Matchup, you can use consecration alone to clear their tokens if they used Muster on turn 4, because there is a high chance that Quartermaster is coming next turn. Do not overextended, spare your Owl for Tirion, but in case you had to use silence before, kill Tirion and use Harrison Jones to counter the Ashbringer.

Ramp Druid: 60/40

Try to control the board, Aldor can be very useful in this matchup. Most of the Ramp Druid decks have one combo in the deck, so try to stay above 14 hp; be aggressive, Druids do not have scary board sweepers, except Swipe. Do not drop Muster on turn 3 (only if you do not have any other choice), because they will Swipe the board, and it will hurt you a lot. It shouldn't be a particularly hard matchup.

My BattleTag is wickedBBQ#2109, if you need advice or have some questions, I can help you out.

Feel free to comment, I'll gladly answer your questions! :)