This is the deck I used to defeat Gothic the Harvester on heroic difficulty today. I will outline the general strategy behind it and reasons why specific cards have been chosen. Please note that depending on your draws you might need several attempts before defeating the boss.
Reason why shaman has been chosen for this match up is his hero ability which can fill your side of the board pretty quickly. Also this particular class has a lot of efficient removal and cheap spells, therefore making it viable against an opponent that overwhelms you pretty fast. Basically your goal is to fill your board quickly and well, keep your Fire/Earth Elementals alive and use Bloodlust to inflict heavy damage.
You may notice that some vital cards are used only once, to be more specific - Earth Shock and Feral Spirit. Reason for this is very simple - I don't have them twice, thus I have tried to somehow compensate for their absence. If you happen to have them both - please feel free to use them instead of other suboptimal cards.
There are some things you need to know about this encounter. Gothic uses at least 3x Abomination therefore you need to make sure that you kill them when he has other minions on board - Unrelenting Trainee f.e. Alternatively you can use the Abomination deathrattle to remove spectral spawns on your side of the board or to trigger your Nerubian Eggs.
Lightning Storm is very efficient against his early Unstable Ghoul and Unrelenting Warrior plays - he usually combines those drops which allows you to basically clear all, because of the Ghoul's deathrattle AOE.
You need to save your hex for the Unrelenting Riders because you have no good way to deal with them otherwise.
Ancestral Spirit and Reincarnate are actually very important cards because he uses Corruption, Shadow Bolt and Drain Life quite often. When defeating him I used those three cards on a single Fire Elemental which allowed me to keep him for quite a while and use him to damage/trade very efficiently. You can also apply it on your Earth Elemental - choice is yours.
Bloodlust is your win condition - use it when you have sufficient dps on the board. If you decide to use the card twice in the deck you can use one of them to clear the board if you are getting overwhelmed. It also allows you to use the spectral spawns to your advantage.
Flametongue Totem can be used to buff the spectral junk on your side of the board and trade them efficiently.
Faerie Dragon has been chosen because it cannot be targeted by your opponent's many spells and is very cheap, allowing you to get a minion which will survive or trade well early on.