Why can't we just give HM attributes to some attacks and remove the HMs altogether?
What I mean is you will still have the HMs if you want to teach them to a Pokemon, but you can use those moves' effects outside of battle using other moves (like Brick Break also has the effect of Rock Smash Outside of battle). So, if you have a certain move, you will be able to use an HM effect outside of battle, but you don't necessarily have to have the HM attack. Obviously, there need to be prerequisites to meet in order to use some effects, but that's easily implemented. That way, we can have attacks other than HM moves and still use them, i.e.:
Obviously, I won't list all the moves for each ability, but here are some suggestions.
Fly to different towns = Fly
Escape from caves = Dig, Teleport, Return (?)
Cross water, climb waterfalls, and pass whirlpools = Surf, Whirlpool, Waterfall (all these moves allow you to use Surf in the overworld) (this will also allow you to climb waterfalls and cross whirlpools, but only after you obtain the proper prerequisites. While surfing, all you have to do is attempt to move through the object and it will happen automatically, without asking a question)
Illuminate dark areas = Flash, Flash Cannon, Signal Beam, Aura Sphere, Ember, Sunny Day, Will-o-Wisp, Doom Desire, etc.
Slice small shrubs = Cut, Scratch, Slash, Night Slash, X-Scissor, Fury Cutter, Dragon Claw, Cross Chop, Karate Chop, Air Slash, Air Cutter, Razor Leaf, Leaf Blade, Guillotine, Vice Grip, Cross Poison, Psycho Cut, Metal Claw, etc.
Crush rocks = Rock Smash, Cross Chop, Karate Chop, Stomp, Brick Break, Crabhammer, Wood Hammer, Rock Wrecker, Crush Claw, Earthquake, Dragon Rush, Power Whip, Vine Whip, Bone Club, Bonemerang, Bone Rush, Skull Bash, Meteor Mash, Needle Arm, etc.
Move boulders = Strength, Superpower, Bulk Up, Focus Energy, Brave Bird, Shadow Force, Power Whip, Vine Whip, Wring Out, Psychic, Confusion, Power Trick, Iron Head, Gyro Ball, etc.
A lot of Pokemon know the moves I've suggested, so you can still make a diverse team in-game without using too many HMs. At the same time, HM moves will still exist if you can't find a match (so you can teach them to your team if you really wanted to).