As Sharjo said, some kind of an Elderwood Tahm Kench with carnivorous plant inspirations could be pretty damn cool.
There's always the possible Void skin, with him being even more monstrous, with purpose and spikes and perhaps a new, special rig for a meaty, spiked tongue, and Abyssal Voyage being a Void rift/portal. Perhaps he could have a third eye instead of a hat, to fill in the silhouette with a way that makes sense for the thematic? Though, that will probably require some adjustments for the animation cycles in which he does things with the hat (when he bows, for example), as well as new animation cycles and rig for the eye. With a Void-ish processed voice, it could either be a very features-heavy 1350 RP skin, or a 1850 RP skin if they decide to go for completely new Voiceover and (maybe) rig instead.
There's also a possible Arcade/Boss Tahm Kench, inspired by Pacman's constant "WAKA WAKA WAKA" jaw snaps. I kind of feel like Tahm Kench and Wario have some similarities which could be explores with such a concept, too.
-_-
Anyways, I may be in love with the concept of Wonderland Tahm Kench, by VegaColors/Ze/ZeOcelot:
http://vegacolors.deviantart.com/art/Skin-Sketches-3-WIP-565706047
Everything about it is just brilliant: From the Passive stacking to slowly form the Cheshire Cat's known smiley face out of thin air (as if he was invisible!), to the colors of the clothing, to the 'hungered' animation. It's all just so good.