The problem is not Patron. It's Emperor. (though I think Emperor is good for the game, hear me out).
Emperor exists as a combo enabler, primarily. He's a very powerful mana engine, and he's neutral. We already see him enabling multiple burst combo decks. That's fine, that's what his design is built for. But keep in mind that with a powerful engine like this, it's usually the engine that will cause problems, not the specific deck that happens to currently abuse the engine to the greatest effect. Right now Patron is "the best Emperor deck" but it's not the only good one, not even close.
So if Patron is taken out with a nerf specific to the deck, it's just a matter of time before a different deck that abuses Emperor comes to the fore. This is particularly true in a slower metagame. Almost certainly, the next deck to break Emperor will be a Malygos deck since (1) we already have very strong Emperor-Malygos decks (2) spell burst has even less counterplay than charge minions (3) Malygos is neutral and they will continue to print damage spells obviously and (4) Malygos combo gains strength in a slower meta.
Alternatively, a druid-Emperor deck could become broken quite easily since FoN + SR is already so strong and Druid is getting a lot of good cards. Emperor enables ridiculous SR turns - we are shocked by videos of an 8 card Emperor-enabled Patron combo, and Savage Roar combos take way fewer cards to become ridiculous and Druid has additional mana burst through Innervate. This is currently only held back by Druid being slightly weak in the current game, though it's still a tier 1 deck! With one large Emperor tick like a Patron deck uses, you could throw out FoN + SR x2 + Innervate + Druid of the Sabre x2 (the new charge 2/1) and OTK any non-Warrior class.
We see this happen before with Miracle Rogue. Ultimately, the engine got nerfed (Gadgetzan). Leeroy nerf was justified because he was too much neutral burst for every class, but Gadgetzan combo still existed and it would have been only a matter of time before a Gadgetzan combo deck was really strong again.
However, I think combo engines are good for the game in moderation. My real answer isn't even to nerf Emperor, but to provide for more counterplay to OTK combo decks in general (counterplay that is more than "kill the combo deck faster than he can put his combo together"). Cards that interfere with your opponent's ability to put together the combination (like discard). Cards that interfere with your opponent's ability to put out a lot of damage in one turn through spells or charges (like Loatheb, but more of this). Cards that guarantee a turn of survival (like Ice Block). And so on.