I'm playing with him alot, Paladin and Druid are strongest IMO (best 1 mana spells [Naturalize basically becomes only a "Draw 1" for killing any critter for 1 with him for example, since you're up a quality creature as well most of the time]).
You need a shell to that's he's just an extra win-con for though, if he's a REQUIREMENT to win, you will lose - but as something to allow extra reach, he can be amazing. (Also note that Druid has the Mech-Bear-Cat that can generate "infinite" parts - I find it not valuable in my Druid-Gazlowe build though)
I'd almost consider Recombobulator a must with Gazlowe as well BTW - since getting an 7/8 reasonably hits reasonably often with him drawing a random mech, and 95% of 8's are amazing [Honestly, if you attack first with the critter probably 100% - is there a bad one besides Al'Akir and with him adding 6 damage after a normal attack....] and 70% or so of 7's. (Also with Recom and Gazlowe both, Clones are handy to have as well - clones to copy good Recomb numbers easily as well as doubling up on free Mechs as well as copying amazing Recombs that are advantageous for the build to copy - i.e. when you get an Antonidas)