I cannot remember the trigger but he definitely appeared super early in my playthrough, even before I spoke to Nettie or visitied the Goblins.
It's possible it was post Skeletons because I snuck past the ruins and broke into the trapdoor down into the area where the mysetrious stranger can be awakened really early doors, but I wouldn't swear by it. I remember at the time thinking, woah there cowboy, i haven't exhausted anything!! Nor did I have the impression that the Tadpole was taking over at all.
So yeah, some timing work needed there.
