I've had an idea for this issue for many years now and still wish it was the one they'd implement ASAP.
Every species of Pokemon is now given 1 or 2 out of 8 possible Field-skills. Those are not moves. The only function they have is a function outside of battles. And using those needs to be unlocked by gathering enough gym badges.
For example, let's say the 8 Field-skills of a game are the following list:
#1 Smashing (for destroying obstacles)
#2 Shining (for illuminating dark places)
#3 Digging (for finding underground caves)
#4 Pushing (for moving obstacles that cannot be destroyed)
#5 Swimming (for transportation across water)
#6 Teleporting (for instantly travelling between places)
#7 Climbing (for getting across osbtacles that cannot be destroyed or moved)
#8 Soaring (for travelling in the sky)
Let's say all Pelliper have the Field-skills Swimming and Soaring. As soon as you obtain 5 badges, you can use a Pelliper to cross water-areas, and after obtaining all 8, you can use it to soar above the region.
In this system, you cannot make HM-slaves as the most Field-skills a Pokemon can have is 2, and there would be plenty that only have one.
Instead you want to make sure your team is at least somewhat diverse and isn't made up of Pokemon with the exact same Field-skills.
You'll want something that can swim eventually, something that is physically strong enough to move big boulders.
But more than one of these would be optional (making it even less restrictive), like illuminating areas or Teleporting, where it is more about being convenient if a Pokemon you use naturally generates light or is a psychic, rather than being necessary to have those to get somewhere or to something.
So if you just make a full team with 6 random members, chances are you'll be able to overcome all overworld obstacles...unless you were making something extremely gimmicky like an all-fish team or one made up entirely of weak Pikachu rip-offs or something. But it would not make you waste move-slots to temporarely un-deletable moves as the current system does.