Hearthpwn

I have yet to win a game against an Armor Warrior.  I was once OTK'd from 35 health and 4 armor.  

Which decks have a chance against it?

You basically have to pressure them down so that they don't have time to play the cards they want to play and instead have to respond to the board.  That being said, it's not easy to do. 

I think "even larger man" paladin might to OK against them, particulalry running Starlight Groove to give your face some protection.  You can always tech in Dirty Rat or Theotar, the Mad Duke (and probably a Rustrot Viper too), but with exception of the viper these cards are generally more of a miss than a hit and will probably tank your winrate against other decks.

Don't feel too down though.  Blizzard printed and absurdly powerful card Odyn, Prime Designate, and the only reason it hasn't been running rampant thus far is that the deck to support it was rubbish.  Oddly enough, now they've buffed pretty much every card it's doing rather well.

At least it's not frustrating to play against though /s

I just barely won my first game against Armor Warrior as Control Priest.  I copied two Heavy Plate cards and an extra Astalor, the Protector for a total of three Astalors.  

Paradoxically, what really saved me was the fact he summoned Tirion Fordring from his 10-cost weapon from Ignis, the Eternal Flame.  I killed Tirion, and he lost his superior weapon.

So in order to win as Priest I had to get 21 extra armor from copied cards, and have the luck that he gave me the means to destroy his own weapon!

An epic fight indeed!

Warrior often struggles with large boards, so like iv said: pressure them with wide boards of 4+ health minions to prevent them from playing odyn and stuff on curve; they'll have to choose between answering board every turn to not fall irremediably behind or risk it and usually pay for it.

Additionally, frequent taunt minions can easily block them out

The best decks against Armor Warrior are the ones which keep the pressure up, so they have to keep playing their armor gain cards to stay alive and can't afford to Odyn. That is, Aggro decks such as Hound Hunter, Mech Rogue, and Pure Paladin.  Other than that, the best deck against it is Chadlock, because Sargeras, the Destroyer clicks "Future minions summoned from the portal have +2 health and Taunt" and they struggle to get a hit in for the rest of the game. 

For Control Priest in particular, your best bet is hoping to Dirty Rat or Theotar, the Mad Duke their Odyn, Prime Designate before they can play it, forcing them to play the attrition game (which they will certainly lose). But this is one of the worst matchups for Control Priest as you can't pressure them out of playing Odyn or heal out of range of their burst. 

I beat it with my kangor paladin deck which runs rivendare and has tons of self healing due to kangor's effect.  Set up rivendare and dance floor then pull all the horsemen out with front lines and rush them. Boom

I was playing blood dk in diamond and it had quite some options to get rid of Odyn with rat, theotar and patchwerk, so the deck had decent win rate against armor warrior just like with sif mage. In legend I switched to fatigue implock and it tempos out armor warrior quite well.