C'thun control warrior. Armor Up! , later Tank Up! and Brann Bronzebeard plus Ancient Shieldbearer should bring you out of any danger. Save the brawls for the anyfins (or at least one for the second). Depends a Little bit whether the anyfin also runs N'zoth, but generally the armorgain is very helpful against the anyfin burst.
Or, as mentioned above, pressure him down. E.g. with Bloodlust shaman or maybe midrange hunter (although I don't know how the matchup is exactly after the CotW-nerf).
Over the past few days I have created a Handlock Priest deck (Still on the search for the unicorn) and it has had a 100% winrate against 4 of these Anyfin decks. Reason? I entomb their warleaders, and won't play them if I draw them. It doesn't kill them, so their 10 mana Anyfin can happen summons 2 2/1 charge murlocs.
Yes, entombing warleaders sucks for tempo and I rather have their lightlord, but I'll just SW: Death that.
Long story short: FInd a way to not kill their minions.
Killing them faster than their combo can kill you is allways a good strategy. Some decks can swap in some murlocs to destroy the enemy tactic. (aggro mage or faitgue warrior can put in the coldlight oracle for example or zoo can put in the 2/1 murloc which spawns a 1/1 taunt)
If you go for the mill deck tactic you should just concede whenever you see an aggro deck..
Rollback Post to RevisionRollBack
Who can take your trash out? Stomp it down for you? Shake the plastic bag and do the twisty thingy, too?
You actually need to do it to both, unless your deck has lots of healing and / or you can reliably keep a taunt in play. First AcH brings back 1 Warleader and 2 Bluegill = clear two 4-health minions. If this Warleader dies, the second brings back 2 Warleaders and 4 Bluegill for 24 damage, usually enough to get lethal, especially with a weapon charge. Add to that that you may well face a third AcH from Ivory Knights, and even one dead Warleader pushes this into extremely lethal.
SMOrc, high-armor warrior with two brawls, Hunter. There you go.
And although Murloc Paladin might look very powerful sometimes, they also have these games where they can't draw anything and just lose in the first 6 turns. It happens more than you might think. Just start playing it, and you'll see for yourself.
If you polymorph or polymorph boar on the murloc warleader they basically lose. Its a tricky deck with all the heals they have, You have to try and save your Dmg and then finish them in a 1 turn burst.