HM's won't be going anywhere. And if they were, an item would not suffice as a replacement for them. Are you seriously gonna carry a jet ski, rock climbing boots, a hammer, helicopter,, etc plus all your other items in your backpack (including your bike)?
The only reasonable way to fix the HM problem would be to do this:
Give each pokemon two different move-sets, say one for battle, and one for out of battle. The first move-set would still have a limit of 4 moves, but the other one wouldn't. You would still come across HM's, but not as an item. More as a level up process that would activate when you accomplished a certain event or made it to a certain checkpoint. When you did this your pokemon would learn for out of battle purposes. (So you second move set would consist of moves like sweet scent, headbutt, flash, dig, surf, rock climb etc). However if you wanted a certain HM move, probably Surf or Waterfall, as an actually battle move, you could go to a little hut and a man would make it so. There would probably have to be 3 or so huts over the region so that you wouldn't have to wait until the last gym city to do all of this. Or you could just have one appear early on in the game.
Of course the pokemon would only be able to have as many slots for out of game moves for as many as they can possibly learn; but my guess is they would put a limit on these two, 4 probably.
