Sooo I've done more thinking, and dreamed up an easy replacement for HMs: this is what I propose:

Skill Tutors
Hidden Machines (HMs) have always sucked. Yet for some reason GameFreak has continued to include them in all their Pokémon games, saddling players with the burden of non-erasable moves on their favorite Pokémon or a dedicated HM slave or two to get through all the obstacles in the game. Not anymore. Mythos does away with HMs completely (some of the moves have been reworked as regular moves) and replaces it with the Key Skill system. Essentially an RPG element, the player will attain Key Skills during the game by interacting with Skill Tutors (who only fulfill this task). Some of the Key Skills require you to have certain Pokémon in your team to work (such as for Teleport or Fly), but the Pokémon itself does not have to be changed. In addition, none of the Skills that require a Pokémon are essential to completing the game (although you will miss some cool things if you don't).

The Key Skills are:
1. Clear Out: This Skill lets you remove shrubs and rubble.
2. Push: This Skill lets you move crates and boulders around.
3. Swim: This Skill lets you move in Water.
4. Unearth: This Skill gives access to the Mining mini-game in Deserts, Caves and Glacial Caves.
5. Fall Back: This Skill lets you instantly return from a non-hazardous location to the last PokéLodge you visited.
6. Dive: This Skill gives you access to Under Water when on Water.
7. Climb: This Skill allows you to climb up certain steep paths, trees & ladders.
8. Quick-Travel: This Skill lets you instantly move to any settlement that you've already visited.

The Skill Tutors are spread out over the world, some are accessed after battles, others at story events, whatever. At first I thought that Fall Back, Quick-Travel and Dive should be Pokémon based, but then I realized that's senseless. Unearth is an important minigame for an extensive Rom hack that I've thought up, very similar to the Mining in the Underground in earlier games.