If I were to pick one of these to actually try, I'd start with 2 just because it's the simplest. However it probably doesn't actually address Gloomy's problems, and it certainly doesn't make him feel like a Call of Cthulhu villain, which I think ought to be the objective.
Frankly, I think I'd remove the Voodoo Pins entirely from his deck, replace them with more Cultists or more Zombies, or with a One-Shot besides Vast Following which can help him draw his Relics faster. But if we're stuck with the deck he has now, I'd say the answer is to...hm, actually just had a neat idea, what about this? It's more complex than I'd prefer, but still fairly sleek, once reduced to a single iteration of the several versions I'm tossing out.
5. Delete the alternate win condition from Gloomy's side 1, and change his start-turn trigger to look in both play and in the trash. This frees up a line on his front side, letting you implement one of ideas 6 or 7, or just add something about voodoo pins if you insist. Meanwhile, his back side now has the "At start of turn, If he didn't flip this turn, and he has three relics, the heroes lose" text I suggested somewhere earlier, along with a way to gain a relic back from the trash every single turn without fail - thus, if you don't keep breaking them (and this should be easier than killing him directly), he will eventually reach three and win on his turn.
6. Move Gloomy's side-A advanced text to standard text, and his advanced text becomes "immune to damage" or "whenever he takes damage, he gains that many HP" or somesuch (though really, it'd be tremendously out of flavor for the Smog in Time Cataclysm to make him more killable, it ought to have the opposite effect).
7. As #6, except the damage immunity is standard text, and he has some completely other advanced effect. This version simply can't be killed; you're stuck fighting his cult until all three Relics have exited the villain deck, at which point it's "go time".