My idea is that you could do the same if you do a quest, meaning that new players would still need the move re-learner npcs until they complete the quest.
Here is my idea of how the quest could work but it can be changed for something different(beetween each step you gotta go talk back to the quest giver):
The quest wouldn't be easy , any villagers can give it to you , you would be able to recognize because i has a black "!".
The quest giver first the first step would require you to go find a move re-learner and relearn one move.
The second stp would be to print a move with a blank tm to then use it on a pokemon.
The 3rd step would be to forget a signature move to then go relearn it on a move tutor.
Once that is done you can go talk back to the npc and it will allow you to relearn move everywhere .