EDIT: Divine Favor turned out to be a dead card quite often, so I replaced both with Blessing of Wisdom x2. A good use for these is either on turn 1 turn 2 on Gothik's first minion or later in the game on the big fat ones (preferably 5/6 Rider). Combine with Humility/Aldor Peacekeeper for great value.
Thanks for posting this deck. I tried to kill Gothik so many times, but he's really difficult without the right draw/deck. Originally I tried using a control priest deck but I used a modified version of your deck using the cards I had. I added Dancing Swords because it's a great turn 3 drop that also bring Gothik closer to fatigue. I also had Leeroy Jenkins for burst damage at the end and an Alexstrasza just in case.