Fairy type appeared in Gen 6. This is the generation that started giving older Pokemon many new toys and gimmicks, in a "Fairy tale" way. We can assume it took a while for Fairy type to be discovered in the Pokemon world, so we can paint a story based on that:
Kanto region has a very long history and is constantly evolving. After many years, foreign technology (especially in regards of Pokemon abilities and moves) has started to enter this region too, bringing new strategies and battle styles. This, however, has rendered some older Pokemon somewhat obsolete, and some of them were already bad to beging with, meaning they became very unpopular and rarely caught or used.
Our protagonist is Karen's (still Elite Four) young nephew and been hanging with her a lot. As a result, he really wants to win with his favorite Pokemon. However, his team happens to be Beedrill, Mr. Mime, Jigglypuff and his starter Growlithe. Living in Saffron City and having limited battle experience, he is completely unable to win against the veteran Gym Leader Sabrina with his team, especially after one day Sabrina powered herself up and brought a Mega Stone for her already strong Alakazam.
That was too much for our trainer. He could never beat Sabrina with his team, no matter how many times he challenged her. The surrounding Saffron cities are far enough to need a full day to go there, challenge the Gym and go back to Saffron. Moreover, Gym leaders from those citys eventually also got Megastones, so while easier than Sabrina, they were still too strong for our protagonist.
His aunt Karen suggested training a Larvitar, but not only its hard to catch and train, our protagonist doesn,t really like Tyranitar. Instead, he asks for a big sum of money (after all, being an Elite Four, Karen is very well paid and wealthy) and goes to other regions, specifically Hoenn, Kalos, Galar, Alola and Sinnoh. He learns a lot during his journey, becomes much stronger and catches 2 new Pokemon, both of them similar to his native Kanto region. Now he is back to conquer Kanto Gyms and tell about his journey.

Item: Beedrillite. Moves: U-Turn, Poison Jab, Drill Run, Roost. Beedrill has always been a very unpopular Pokemon. Aside from Bug Catchers (who are not considered exactly strong trainers in Kanto, though Bugsy is close), no one ever used Beedrill due to it being extremely weak. However, in Hoenn, our trainer learned that Beedrill is one of the few Pokemon who can Megaevolve and searched its Megastone for a long time, before finally finding it at one of the Battle Tents that are througout the region. It became one of our trainer's strongest Pokemon and his lead in battle. Beedrill uses U-Turn to deal strong damage and escape, having Poison Jab as second STAB and Drill Run as coverage. Whenever Beedrill manages to face a Grass Mon, it can heal with Roost. From one of the worst Kanto Pokemon, Beedrill suddenly became a big threat, it has its fairy tale.

Moves: Stealth Rock, Dazzling Gleam, Tri Attack, Helping Hand. Like Beedrill, Wigglytuff has always been a very unpopular Pokemon. Moon Stones are limited and Nidoqueen, Nidoking and Clefable were much more viable choices to be used on, especially after it was discovered Clefable could have Magic Guard and Unaware abilities. By the time our trainer left Kanto, Fairy type was known in Kanto, but since no one used Wigglytuff in serious battles, no one bothered to check its Fight, Bug, Dragon and Dark interactions, so it was considered a full Normal type. Out trainer discovered in Kalos that Wigglytuff there is very respected due to being a Fairy type and since then, decided to specialize in the type, since he knew Kanto had no Fairy type expers. After finally using the Moon Stone, with the new typing, our hero got to challenge a Giratina during his journey and easily won the battle, but thats not what we are here to tell about. From several competitive trainers, our guy learned that Stealth Rock is a good move and taught it to Wigglytuff along with 2 STAB moves. Last slot is Helping Hand, reserved for Double battles, which sometimes are fought.

Moves: Calm Mind, Dazzling Gleam, Psychic, Shadow Ball. Only the dreaded Sabrina still used Mr. Mime in Kanto, no relevant challenger tried to make it work, since there are many other Psychic Mons. This also meant, that like Wigglytuff, no one used it against Lance's Dragons. When our trainer arrived to Galar, he saw that Mr. Mimes there are Ice Psychics, being much better than Kanto Mr. Mime. Still, he decided to keep using his old pal, especially since he knew since visiting Kalos that Kanto Mime was Fairy type. He taught Calm Mind, STABs and Shadow Ball to Mr. Mime in order to have the advantage vs Sabrina's Psychic.

Moves: Dark Pulse, Foul Play, Play Rough, Pay Day. Our trainer has always wanted to have a Persian. However, after years of many criminals (especially the infamous Team Rocket, leaded by Giovanni) using the line in Kanto, an extermination campaign was launched around Saffron and as a result, Meowth became very rare there. When our hero arrive to Alola, he quickly found a local Meowth and added it to his team. It soon became clear that Alolan Persians are much better than Kanto ones, especially in terms of bulk. This one uses 2 Dark moves, a Fairy move and a move to get more money from other trainers in order to keep financing the journey.

Moves: Hypnosis, Confuse Ray, Blizzard, Moonblast. Despite being a Fairy type, Comfey wasn,t liked by our trainer. When he was about to leave Alola, someone mentioned that there was a strong Fairy Mon on the top of Lanakila Mount. Intrigued by that fact, he climbed and explored the cold place, discovering Alolan Ninetales. Cautivated by her (75% female chance) beauty, our trainer challenged the fox to a battle and with Arcanine's type advantage, managed to win despite the heavy snowfall. This Ninetales uses both status moves and offensive moves to disrupt and defeat all her opponents before they can even move. Note from author: Ninetales doesn,t learn Moonblast in LGPE, but I don,t care, since it makes 0 sense, the move is present in those games.

Moves: Flare Blitz, Play Rough, Superpower, Teleport. In Sinnoh, the last region of the journey, our trainer encountered a strange blonde guy, who why looking young, behaved like he was much older. This strong trainer had an Arcanine too, but it was very different from Kanto one, having a type advantage too. After being defeated once, our protagonist trained his Arcanine to overcome the rocky Sinnoh one. This was achieved by being faster (95 base Speed compared to 90) and learning Superpower. Despite winning the Arcanine duel, our hero still lost the rematch against his misterious opponent, who this time tried to punish him for interfering in his evil plans. Fortunately, our hero's Arcanine knows Teleport, saving him from the demise. The move also works in some battles to bring Mega Beedrill safely to the field.
Our trainer has gained a lot of strength and experience during his journey. Will that be enough to conquer the now very strong Kanto Gyms? Only time will tell.