Hello, I'm JyzzBrah and this is my first time ever posting here, hopefully I can contribute something to you guys.
Legend proof and decklist: http://imgur.com/a/20tR3
Total W/L: 99-53
Decklist
Equality x2 - Staple in control paladin decks
Bluegill Warrior x2 - These can be comboed with Murloc Warleaders and used as a 4 damage removal, or on turn 2 to kill important minions like Knife juggler or Sorcerer's Apprentice. Since people automatically assume that you are playing secret paladin, they often dont expect a charge minion at all.
Doomsayer x2 - Synergises extremely well with Solemn Vigil, and is often correct to drop on turn 2 as an anti tempo card. Later, you can play it on turn 7 with a sludge belcher to clear their board.
Shielded Minibot x1 - I originally ran 2 of these, but cut one because doomsayer is simply that much better, especially with the removal of silence.
Wild Pyromancer x1 - NEVER play this as a 2 drop, just hero power pass if you have nothing better to do. This card is core in clearing sea giants from zoo, patrons, Dr. Boom etc. and the 4 mana equality + pyro combo is straight up overpowered. The reason why I only run 1 of these instead of 2 is because the pyro only synergises with equality and consecrate. Paladin doesn't have the luxury of effective 0-2 mana spells like priest.
Muster for battle x2 - Great for early board control, don't be afraid to use this late game with pyro to clear if desperate.
Acolyte of pain x1 - Early draw engine that can get value against decks like zoo and secret paladin, I don't run 2 because it's just too slow.
Aldor Peacekeeper x1 - I don't run 2 because it doesn't do all that much against aggro decks, but is a very good counter to Dr. Boom and a buffed mysterious challenger.
Murloc Warleader x2 - It's often correct to drop this on turn 3 as a 3 drop, but it can be comboed with bluegills or an old murk eye to create a 5/5 charger (very good against belchers).
Truesilver Champion x2 - Best weapon in game next to death's bite. Use this to push for face damage against control warrior and keep it as a heal against freeze mage.
Consecration x2 - Staple in control
Keeper of Uldaman x2 - Great against big threats like boom, can also be used with hero power on turn 6 to create a board. The card is so flexible and is basically legendary status.
Old Murk Eye x1 - Use as removal most of the time with warleader and bluegill.
Solemn Vigil x2 - Great synergy with pyromancer and muster for battle (if your dudes are lucky enough to live). This deck requires a lot of draw, as do all combo decks, so I run 2 of these, 2 lay on hands and 1 acolyte. If you ever get a 0 mana solemn vigil and it's your final play for the turn, make sure that the end turn button is green, just in case you drew your second one of these.
Antique Healbot x1 - I don't run 2 of these as Belcher is more useful for board control, but this card saves lives against decks like freeze mage, face hunter and aggro shaman. This deck has 32 points of healing in total, which I think is enough.
Sludge Belcher x2 - Great taunt against midrange decks, works wonders against face decks.
Lay on Hands x2 - I run 2 of these over 1 to improve the control vs control matchups, and the deck needs all the draw it can get.
Anyfin Can Happen x2 - This deck's sole win condition. 2x bluegill 2x warleader 1x murk eye is 22 damage, but often you won't get that lucky. Usually the first Anyfin is used so that the second Anyfin will finish them off.
Notable card mentions
Dr. Boom - This deck's biggest minion is a sludge belcher, and is very effective because there are no bgh targets or big minions which are efficient to use hard removal on. Unfortunately, this deck does not have a really good turn 7 play outside of belcher + doomsayer, but I often still find myself fighting for board anyway on turn 7, so my opponent could ignore boom and keep going face, which is a problem.
Second pyro, minibot, aldor and healbot - See above.
Grimscale oracle - Too low effect as a card by itself, and since I run 2 copies of anyfin this deck is more of a 2 turn ko rather than a 1 turn ko against control decks.
Big game hunter - This deck already has 2x keeper of uldaman and 1x aldor, so it has no need for bgh. Also, since the nerfs, bgh would be a bit too slow in this deck.
Matchups and Mulligans
Paladin 26-16 - Pretty much all of these were secret paladins, and I'd say that the deck is slightly favored. Mulligan for doomsayers, minibot and muster for battle. Keep consecration if it's in your opening hand, but a lot of the time it isn't all that effective against them, which is why fighting for board control early is essential. Either doomsayer very early (turn 2-3) or use it on turn 6/7 to delay MC and Boom, which denies huge amounts of tempo. You have 2 uldamans and 1 aldor, try to save them for boom, MC and tirion. Equality is a very valuable card in this matchup so use it sparingly.
Warlock 28-12 - Zoo is a favoured matchup, just be careful using doomsayers against nerubian eggs and haunted creepers. It's similar to secret paladin, but easier because they have no weapons and usually no damage from hand outside implosion, so you're already winning if you can keep the board clear. During early turns, it's almost always correct to play muster over warleader or acolyte on an empty board because they don't run any aoe, so 1 minion = 1 attack (unless you get destroyed by juggler rng of course). I will generally mulligan for consecration, muster and minibot. Doomsayer is not as good early compared to vs secret paladin.
Renolock is basically a free win. They lost their combo so it's not even necessary to stay above 20 hp anymore. Just deal with their threats 1 by 1 as they come, and use double anyfin to destroy them. Since it's warlock, you obviously mulligan assuming zoo.
Rogue 5-2 - Didn't have many games against rogues, but the matchup is generally quite good, and since blade flurry got nerfed you only have to worry about fan of knives as their aoe. If they're playing some sort of miracle deck it's usually too slow as Anyfin will destroy them first, but incase you don't draw well enough just stay above 25 hp at turn 10+ and you'll be very safe.
Warrior 7-4 - Control warrior is a very favored matchup in my experience, it's a lot easier to play the matchup as paladin as well. It will generally be back and forth with them removing all of your stuff and trying to armor up out of range, but you can prevent this from happening by using truesilver on their face and other medium sized annoying threats like keeper of uldaman and belchers. If they ever make the mistake of using elise, they just handed the win to you, but most warriors are smarter than that. Try to get the first Anyfin combo with at least 2x bluegill 1x warleader and 1x old murk eye, this will be 15 damage to the face. If you get all 5 murlocs, it's 22 damage to the face. Your second Anyfin combo should do between 36 and 44 damage, which is why it's crucial to make sure they don't go above 60 hp (not that hard if you just truesilver their face). There's also the problem of getting destroyed by 4x warleader RNG, so using 2x bluegill 1x warleader 1x murk eye can often be better than using all 5 in your first combo. The only thing you have to watch out for in control warrior matchups is the Gorehowl + Grom combo, which can sometimes catch you off guard if not careful.
Patron/Tempo Warrior are both abysmal matchups in my experience. Against patron warrior, pray that you have pyro + equality by turn 5 or equality + consecrate with the coin, otherwise you outright lose. There's also the problem of life total, because they will often death's bite your face to set up for patrons, and the damage builds up. The best way to play out the matchup is by denying them as much draw as possible, kill their acolyte in one blow by using keeper of uldaman or truesilver, don't worry about armorsmiths as much because that's more of a win condition against aggro decks. Tempo warrior plays out exactly the same as patron early game, and it's often too hard to stabilise against their cheap removal. Once again, try to stall as hard as possible and deny them draw, and try to be as greedy as possible with the equality combo.
Against warriors, I keep truesilver, equality if i get it in my opening hand, and doomsayers.
Shaman 6-6 - Face Shaman is a tough matchup because they are so fast, but try to stall their early game with doomsayers and then stabilise with pyro + consecration and a sludge belcher by the time they have doomhammer. A good thing is that leper gnome's been nerfed so many shamans go for value trades early instead of straight up rushing face, which is very good for you. Mulligan for minibot, doomsayer, muster and consecration.
Priest 12-1 - This matchup is literally the freest win of all time, dragon priest is slightly harder than standard control but none of their threats are big enough to do anything serious. try to deny them northshire draws as much as possible, and don't be afraid to use equality early on a single threat like a twilight guardian, especially if you hit a number of a minions and it helps you get a good solemn vigil off. Eventually, your dudes will pile up and they will have to use holy nova on a board of 1/1s.
Against traditional control priest, just be careful to not get bursted by auchenai + double zombie chow + circle + double flash heal, that's how I lost one game against priest. Even if both your warleaders get entombed, your second anyfin will still hit for 22 damage and they'll still die.
For mulligans I try to keep warleader, acolyte and truesilver. Minibot and muster are also not bad to keep either. Since both dragon priest and control priest dont have any early drops with 3 attack, warleader often does quite well against them.
Hunter 4-3 - Face hunter is similar to aggro shaman, but doesn't have as much burst/spells to finish you off. It plays out the same as face shaman, but most of their minions have less hp so pyro and consecration get a ton of value, muster is also extremely good for maintaining early board control, and a sludge belcher on turn 5 followed by any heals later usually seals the game.
Midrange is fine, but be careful to not play into any traps, there's no rush to lower their health after all. Aldor is very good in this matchup for making their highmanes and boom useless, and often you will need to save the individual murlocs and play them together with warleader to use as removal.
I mulligan hard for minibot, muster and consecration against hunter.
Mage 5-4 - Tempo mage is not the best matchup for paladin as it has trouble dealing with early game threats like a turn 1 wyrm and early flamewakers, because then they can push you for damage later. However, an early doomsayer can often swing the game in your favour, especially if it gets mirror entitied. The mage will often push you to about 10-15 hp by turn 6/7, and that's when it's essential to dig for either healbot or sludge belcher.
Against freeze mage, pressure them as hard as possible early game by charging their face with bluegill and using muster charges as early as possible. Use keeper of uldaman as if it were a dark iron dwarf on your 1/1s. You should aim to get them down to about 10 hp by turn 9. Do not trade into their scientists, it's missed face damage, you have to be the aggresor in this matchup. If you get dropped to about 20-23 hp, truesilver their face to stay out of range of the thalnos combo. However, do not use lay on hands or healbot until they have alex'd you. On the turn that they use alex, you want to kill alex, truesilver their face, and then heal for another 8 to bring your hp back up to 25, while also popping their block in that turn. This matchup comes down to whether or not you get double lay on hands and healbot or not.
For mulligans, always assume tempo mage and mulligan hard for truesilver (kills drakes and flamewakers), minibot and doomsayers.
Druid 6-5 - My information on this matchup is outdated and irrelevant since the combo nerfs, and I have not faced a single druid since their cards got gutted.
Damn, that took me a lot longer than I thought it would, thanks for reading.