Hearthpwn

This is the deck I used to beat Heroic Atramedes. Just as a side note, I loved raiding this boss when I played WoW, the idea of a blind dragon and you had to sneak around and avoid his sonic abilities was really fun.

The key to this boss is managing his weapon and surviving his huge attacks. I picked a controladin because you usually only play one card a turn and you can still pump out dudes with your hero power without the drawback of making his weapon stronger. Also, paladin has some big heals to survive if you do get hit hard (and you probably will, I did.) So here's the breakdown of the cards I picked.

Acidic Swamp Ooze - Cheap weapon removal. Make sure to use it when his weapon is around 4 attack or higher because he will re-equip it his next turn and it does you no good to get rid of it at low attack. I put two copies because of his ability to re-equip right after you destroy it, 1 copy wasn't cutting it. Watch out for Sonic Breath,  it really buffs his weapon and is a perfect time to use ooze.

Harrison Jones - Less cheap weapon removal but great for card draw. You'll be getting about 4 cards at least when you use this.

Sen'jin Shieldmasta & Sludge Belcher - Great midgame taunts to soak some hits clean his board up some.

Lay on Hands & Holy Light - I don't think you would be able to survive without some healing. I think 1 copy of each works just fine.

Wild Pyromancer + Equality - Use this combo after he plays Onyxia to clean the board right up. His weapon will grow quite a bit when you use this combo so I would be hesistant to play another card after, just hero power.

Big Game Hunter - Great for picking off Drakonid Crushers, or even Onyxia.

I hope this guides you in the right direction, please feel free to leave suggestions in the comments section based on your experience with Atramedes!