I was inspired to try out Control Paladin after reading this great Reddit post (?!) by 星辰之沙(sand of star). They're a long-time Control Paladin diehard. Akin to Zetalot as Priest, ApxVoid as Mage, or Fibonacci as Control Warrior; Sand of Star is a one-Hero player and we can trust that they have "explored the space" of Paladin options. A decklist from before Rastakhan appears here:
Code: AAECAcOfAw7SBJAHs8ECucECycIC08UCiMcCp84Cq9ACjtMCy+wC2f4C8f4CoIADCNwD9AXPBvYHm8ICi+EChPwCkYADAA==
1x Crystology
2x Equality
1x Hydrologist
2x Wild Pyromancer
1x Gluttonous Ooze
2x Stonehill Defender
2x Consecration
1x Meat Wagon
Lx Spiritsinger Umbra
2x Truesilver Champion
2x Carnivorous Cube
Lx Harrison Jones
2x Mechano-Egg
2x Shrink Ray
Lx Zilliax
1x Mossy Horror
1x Nerubian Unraveler
1x Spikeridged Steed
Lx Sunkeeper Tarim
Lx Kangor's Endless Army
1x Lay On Hands
Lx Uther of the Ebon Blade
Yikes! Like most Control decks, it's heavy, with a lot of high cost cards; and expensive, packing six Legendaries and seven Epics.This is tuned for high Legend level play, and doesn't work down in the soup with folks like me at Rank 15. But the ideas of the deck are sound regardless and we can make some tweaks to get it right for lower ranks, as well as refresh the concept for Rastakhan's Rumble.
You can see all the 1x, even with Commons, and this definitely tips the hand that this build is for late-game play. You want the right card, but you don't need it right away. Most of the early game cards are focused on surviving a rush. Equality, Wild Pyromancer, Hydrologist to get a cheap Secret to feed the Pyro, and Stonehill Defender are all about not dying by turn 4. Assuming you make it to turn 5, you are looking for Consecration, Mossy Horror, Sunkeeper Tarim, or Shrink Ray to asymetrically reset the game, stabilize and grind to a win against aggressive decks. In my experience, they concede if you are 15+ life on Turn 8 or higher. If they don't, start playing around the Leeroy Jenkins they have in hand. All these cards have reasons, and the post linked above explains them well. But for where I am, I can dump a lot of this and still have a lot of success and fun making big robots and dancing with the devil while watching my life total.
You need to keep the board management stuff. You need to keep the Mechano-Eggs and/or Mechanical Whelp, and you want to make sure you can dress them with either Zilliax or some other decent Magnetic Mech. You want Carnivorous Cubes as well to guarantee they die, and Kangor's Endless Army to get them back in cool form. But the Nerubian Unraveler can go—it's there to beat Druids (hard to cast a 12-mana Ultimate Infestation when your hand is low) and Mecha'Thun Priests (they depend on a 10-mana turn that needs Twilight's Call to cost 3, not 5). Spiritsinger Umbra is overkill and underwhelming unless you get the magical Umbra-into-Meat-Wagon-into-Egg-into-8/8. Your weapon removal doesn't need to be Harrison Jones and Gluttonous Ooze. And so on. You can port these themes to budget options and still have a good time.
What changes does Rastakhan bring? Well, the hero-healing aspect of Paladin has been dialed up as a theme. Between Zilliax, Lay On Hands, and Truesilver Champions, you'll get 10 life restored, and that makes this an option:
Zandalari Templar Rare 4/4 Minion for {4}. Battlecry: If you've restored 10 health this game, gain +4/+4 and Taunt.
I like 8/8 Taunts, and I like it when they cost 4.
Also, Paladin, for whatever reason, was deemed worthy of Ice Block. It isn't a Secret, but you know when to cast this in today's OTK-heavy meta:
Time Out! Common Spell. You are Immune until your next turn.
Even beats the (bad) Temporus deck that's been bandied about!
Paladin also gets an excellent early-game card that's worth it even if you only get an extra 2 life from a Truesilver hit:
Crystalsmith Kangor Legendary 1/2 Minion for {2}. Divine Shield. Lifesteal. Your healing effects are doubled.
Small Legendary minions are tricky to get right. You want them good enough to play, like original Patches the Pirate, but not that good; and you want them weak enough to pass over sometimes, like Bloodmage Thalnos, but not so weak they never see play, like Patches now. This gets the mix right, I think. The effect gets better with decks that want fewer small cards. It's a nice effect, but you can do without it. Swapping this in for a Hydrologist is easy enough. With the bubble and Lifesteal, it represents at least 4 life, and potentially a lot more if it gets dressed by Steed, appears after you have Uther's blade, &c. Could mess up your Meat Wagon math, though, so your mileage may very.
HEARTHSTONE has been tough the last couple of months. I was pretty burnt out on the metagame and I wasn't the only one. But I'm heartened to see a little light at the end of the tunnel. At first glance, it looks like there are decks that survive a weenie rush and still have tools to kill OTKs, without being one of those kinds of decks. Let's see how it plays out.