This is the deck I beat Heroic Archaedas with on my first try (Super lucky)
Go for huge bursts and don't worry too much about board control since he'll just use his Shattering Spree.
Using Soul of the Forest before Shattering Spree will give you a full board of 2/2s so you can Savage Roar to victory.
Only try to control the board if you're scared of getting bursted down by his spells.
Naturalize: Hard removal that can mill your opponent if he's not careful.
Mark of the Wild: +2/+2 is great both on statues and on your minions, gives you great trades and more power to get close to lethal range if needed.
Power of the Wild: The strongest card of the deck, +1/+1 across the board is ridiculous considering your board will have a ton of minions at all times.
Wrath: Great for cleaning up Pit Snake or just helping clear a Taunt.
Mark of Nature: You're mostly going to use this for the +4 Attack and not for the +4 Health/Taunt.
Savage Roar: I don't need to explain this card, but it's the burst you'll usually need to win the game.
Mounted Raptor: It's good to proc Sacred Trial since it gives you a 1-drop anyways.
Soul of the Forest: One of the most important cards of the deck. Gives you a full board of 2/2s if Archaedas is dumb enough to use Shattering Spree when you have some statues left.
Swipe: The fact that you can use this to do 4 damage to the face is great, and one of the main reasons I use this card.
Keeper of the Grove: Another all around card, can kill Dire Wolf Alpha and Silence Taunts/Buffs.
Force of Nature: Anyone who plays Druid knows that this card is excellent both for cleaning up the board or dealing a ton of damage to the face.
Ancient of Lore: Either you draw 2 cards or Heal for 5. Great all around card. Use it depending on your condition, also try not to proc Sacred Trial with this guy, the 5/5 body is extremely good.
Abusive Sergeant: This card is the one that won me the game several times against this boss, try to get it in your opening hand, but don't play it on turn 1. You can also use it to proc Sacred Trial
Dire Wolf Alpha: Great to set up between statues, gives you favorable trades if you take positioning into account (Which you should)
Lance Carrier: +2 Permanent attack buff. This card is great to buff Statues and to proc Sacred Trial, also the 1/2 body can help clear the Pit Snakes and it usually gets targetted by Shattering Spree.
Potential cards you could use:
Big Game Hunter: Instead of Naturalize, it gives you a 4/2 body and also removes Earth Elemental
Poison Seeds: This card could potentially avoid you a ton of damage from the Shattering Spree. You can also combo it with Starfall on Turn 9.
Starfall:See above, only use this card if you're using Poison Seeds.
Cenarius: Give all your minions +2/+2 is great since you're gonna get statues every turn anyways.
Doomsayer: Hard removal on the whole board, might eat a spell that would otherwise be aimed at your face.
Dark Iron Dwarf: Basically a more expensive Lance Carrier if you don't have it.
Ironbeak Owl: All around good card, the 2/1 body can be buffed with Power of the Wild and it can silence anything he decides to throw at you.
Cards with possible Synergy:
Master Swordsmith: Giving +1 attack to the statues is good, but kind of unreliable.
Sunfury Protector/Defender of Argus: Taunt-givers, Argus is better than Sunfury in this case.
Mind Control Tech: He'll generally have 4 or more minions, try and get that Earth Elemental. Kappa.
Enhance-o Mechano: Play this and Savage Roar and you might just win the game with Windfury, or stall it long enough with Taunt and Divine Shield.
Video guide without commentary now included! I took the Board Control approach this time.