If I'm playing Patron, I just concede when I see Shieldmaiden. That's how bad the matchup is. One of our win conditions is easily countered by Execute, and the other is easily countered by Brawl. Once that's taken care of it's pretty hopeless.
I've stopped running Berserkers because they're so easy to take down. People talk about destroying slow decks with them, but there's nothing that stops someone from killing a Berserker in a myriad of ways before it becomes a problem, and because Warsong Commander is nerfed, you often don't even get a chance to hit with them, so there's no point in blowing a big combo to buff them up.
Instead, I've been running Shade of Naxx, which has the same purpose of building up over time, but Stealth protects it from every offensive measure in the game aside from Lightbomb if it survives a few turns. As you know, if a Priest wants to blow Lightbomb to take out a Shade, that's great, because Lightbomb is the big Patron counter as well.
The Shade has also makes people panic, since it's like a time bomb they have to deal with. I think it will help me against Reno decks, because the burst potential of my board increases the longer Shade is there, which means Gromm + Inner rage + Shade can start doing 18+ damage in one turn.
Against other decks, the Shade makes a great trading tool that lets you save Executes. Against a Freeze Mage, a Shade killed Antonidas so I could use Execute on a Doomsayer later on. Against a Druid, it killed Dr. Boom. Etc. I'm liking it a lot as a versatile tool.
Also, the best part about Shade is why I added him in: he won't die in most matchups until you want him to, but he still takes some AoE damage from various stuff going on. as a result, you always have 2 draws guaranteed from Battle Rage; one for Shade, one for you. Against aggressive tempo decks, I found it hard to keep minions on the board to Battle Rage, and bad hands screwed me over a lot. (You know those Battle Rage, Battle Rage hands). Shade of Naxx helps that situation out, too.
I also use two Dread Pirates, two Sludge Belchers, and two Unstable Ghouls to help with anti-aggro decks, and I haven't lost a game vs. aggro since I made these changes. I don't feel like I am any worse off in any of my matchups, either.
Yeah, give Murlocs to Priest. Keep them away from Shaman. Please Blizzard.
That 2/5 Shaman Murloc must be one of the worst cards in the game.
