I came up with this deck after having tried to beat Atramedes with secrete paladin a few times. I made some adjustments to better suite the fight and I won on my first attempt.
To win the fight make sure not to play cards when its not necessary. Be smart and use your hero power instead of summoning minions with cards. Use Acidic Swamp Ooze to remove his weapon when you wanna play more cards on a turn. Use Coghammer to force him to hit your minions. You should easily get to a stage where you can play your Mystic follower.
You can replace Tirion Fordring with any card you like I didn't use him when I won. But if you have him he is a great card.
Remember that you can finish him with Eye for an Eye should it be necessary.