Maloriak annoyed me pretty hard, so I decided to use some cheap tricks on him.
This deck abuses the AI bug with Kel'Thuzad and Taunt minions:
The AI will simply not attack at all if you have Kel'Thuzad + a random Taunt minion.
Everything this deck does is stall until you can drop the absolutely imbalanced combo of Kel'Thuzad + Goldshire Footman (new meta!). Since you should be fine from there, just remove his taunts with spells/minions and happily bash his ugly face in.
Mulligan for cycle cards (Scientist, Coldlight, Arcane Intellect etc.). Usually you should throw everything else away. You CAN keep Kel'Thuzad if you want to avoid him ruining your day because he is the last card of your deck.
Do everything to mitigate damage as much as you can. Maloriak will usually ignore your stuff and go face, so you can freely play minions and hope he wastes his direct damage spells on them. Don't be afraid to use Ice Lance on a minion to save some life, you don't need it for face damage.
Things to mind:
He has 2x Imp-losion and 2x Drain Life, you want to avoid him killing your precious Goldshire Footman with those, so be sure to bait them out beforehand if possible. Be sure to drop the second Goldshire if you can to avoid such circumstances.
He also has Polymorph which he will most likely use on your Kel'Thuzad if he has the opportunity. It can be baited by any creature just like the other removal, Maloriak is stupid and spams it when he has it. Kezan Mystic is also very helpful if you manage to steal a Counterspell because it provides another failsafe against his annoying spells.
If he coins out his Aberrations on turn 1, spare yourself the annoyance and restart. It is very unlikely that you have enough time to set the combo up in this situation.
You can also use Annoy-o-Tron instead of Goldshire Footman if you want to be safe against him maybe removing your Taunt with a spell, but the Kel+Taunt combo comes one turn later with those, which can be critical.
If you don't have Bloodmage Thalnos, I would suggest replacing him with Novice Engineer to cycle some more. He is not that important. Same goes for other support cards like Kezan Mystic (although I find it useful to get his Counterspell). Unfortunately, the most expensive non-adventure card Ice Block is not easily replacable and you will need a lot more tries without it.
Good luck killing him! Pic related.