Hearthpwn

This is the deck I used to kill Gluth with. It is a fairly simple strategy: most of the minions already have one health, so his ability doesn't do much. Just try to keep board control and use your hero ability to keep card advantage. I won first try with this deck. The Oozes are absolutely essential. If you don't draw them, you may just end up losing early.

Be careful of his Unstable Ghouls and Abominations, as they will wipe your board. When I played him, he put three Unstable Ghouls out, so I was able to get them to chain kill each other. If you can wait for them all to come out, this is a good way to clear his board early.

While the Voidwalker may not seem that great, since it will become a 1/1 almost immediately, it is a good stall card, especially if Gluth has a weapon out that you can't destroy.

For substitutions, I would only put in minions with 1 or 2 health, otherwise you are losing too many stats to Gluth's hero power to make the deck economical. Any 2 health creatures need to have purpose or aspect that offsets the 1 stat loss. Flame Imp might be a good addition, and you could throw in some Hellfires if you are having trouble with early board clears.