Astro City does this for essentially all of the superpowered characters. Because the series is written as if there is a longstanding continuity (which there isn't), most people are introduced in one issue and will have their origins explained many issues later, if at all.
Paulie in Deadly Class. Having never appeared previously, he runs into Marcus during finals and insists that he's always been around, is friends with everybody, and is known for his lucky red shirt. Amusingly, he makes it through finals unscathed, and goes on to have a cozy spot as Viktor's Yes-Man by the class's sophomore year.
This trope was the favorite approach of Carl Barks when introducing new characters in the Disney Ducks Comic Universe, and several of his successors take similar approaches. Characters like Uncle Scrooge, Gladstone Gander, Gyro Gearloose, Neighbor Jones, John D. Rockerduck and even the Beagle Boys were all introduced in stories that treated them as if they'd always been there, just not on-page (though Scrooge admittedly is introduced as a solitary miser who hardly ever gets in touch). In this case it works, largely because the Duck comics tend to be standalone stories that operate on Negative Continuity.
This approach is also used by Italian authors: Brigitta McBridge is stated in her debut story to have known Scrooge since at least 1898 (back when Scrooge had moved to Whitehorse and became a businessman), with a later story showing their first encounter actually dates to when Scrooge was a prospector and had just struck rich; Jubal Pomp debuts as a recurring annoyance of Scrooge, and a later story actually puts their first meeting at the same time as the one between Scrooge and Brigitta; and Gideon McDuck was presented as Scrooge's younger brother (this was many years before The Life and Times of Scrooge McDuck was published. Nowadays Gideon appears from time to time, but his relation to Scrooge is left out).
Often writers would introduce a new relative of the main characters stepping by and causing trouble, only unknown to the reader but familar to the characters. Most of them are on-off characters anyway, but some stayed as recurring characters like Gyro's nephew Newton. One of the most successfull characters of that kind may be Rumpus McFowl by William van Horn, with his debut story showing Donald and his nephews in horror on his arrival (which makes for some comedic moments as the readers don't know anything about that character). Later stories reveal he's Scrooge's half-brother instead of his cousin as previously thought.
In the Doctor Who (Titan) Twelfth Doctor story, "The Swords of Kali", a character named Tiger Maratha is introduced who was supposedly a companion of the Fourth Doctor, only to be instantly killed off by the story's villains.
Invader Zim (Oni): Played for Laughs with a deceased Irken named Thoob in Issue 46. Apparently, despite him never existing in the series proper or not even appearing until that issue, Zim liked him enough to devote a shrine to his memory and outright mourn him, in contrast to not remembering established characters Skoodge and Tak when GIR mentions them.
Miracleman: Back in the comic's Marvelman days, Marvelman's archenemy Dr. Emil Gargunza debuted in the 26th issue, the story in question treating Gargunza as if he was a previously encountered enemy of Marvelman.
Phaidor in Pathfinder: Worldscape is introduced in Volume 3 where she is revealed to be the one that turned the city of Shareen into The Theocracy by converting its ruler Camilla to the Cult of Issus, which was made Shareen's state religion. Despite her importance to the background, she was present or alluded to in Volume 1 which showed Camilla's rise to power. This also retcons a minor bit of the backstory where it originally states Camilla pretended to be the same race as Phaidor's to empower the Cult of Issus.
Dulcy the Dragon was fitted in with nothing more then a small back-up story introduction which gave her backstory and essentially went "She's been part of the Freedom Fighters all this time! Honest!" Post-Super Genesis Wave, Dulcy has been reintroduced to the (extended) cast. As this was in a story arc that added several characters, and showed flashbacks to her introduction (in the past of the new universe) it was less jarring than the first time.
Lampshaded example when Dr. Eggman meets a leader of one of his armies known as Axel the Water Buffalo. He's quick to say he recognizes him and recruits him in trying to get to the Death Egg II. Orbot's quick to point out that they've never seen him before and Eggman has already figured that out - he admits that he was too hasty in stopping Super Sonic's Chaos Control, and realizes that a lot of the universe has been altered..
The Transformers (Marvel): Originally, Sparkplug Witwicky's teenage son was named Buster, and he was clearly supposed to be the same character as Spike Witwicky on the TV series. Four years later, Hasbro released the toy Fortress Maximus, who came with a figure named Spike Witwicky. So, in the comics, Buster was suddenly revealed to have an older brother named Spike who had been away from home all this time.
The Marvel series also did a lot of this with introducing new characters whenever their toys came out. The Decepticon Pretenders are particularly obvious, because the six of them are claimed to have been there all along among Scorponok's crew.
Played straight in The Transformers: All Hail Megatron, because Scourge (who makes his IDW debut here) is part of the neutral dead universe faction of Transformers, despite all of them being established in a past miniseries, Scourge just shows up among the casualties, and the narration hints he was there all along.
The Transformers: Combiner Wars: Due to the new combiner toys getting shilled out, Blackjack and Off Road show up amongst the Stunticons just in time for their inevitable combination. While Off Road is addressed as being the new guy on the team, Blackjack's treated like he's been there all along, which is odd considering in issue 2 Blackjack was a member of the Secret Police assigned to the Stunticons.
