More than anything else I think it would be easiest if the moves had different types and were actually good. It wouldn't take much really only surf/waterfall and cut/strength share a type and the only weak move of the bunch is cut. Seeing as strength has always been represented in game as the ability to move rocks and the attack was originally throwing large rocks at pokemon it could probably be changed to rock type which would also at long last give rock type a 100 accuracy move. The only weak move of the lot is cut so maybe up it to around 65-75 power so it isn't too strong in the early game but isn't useless late game (maybe make it bug type too because it is used to remove plants something bugs do well)
I'd be all for this. I like the HMs. Partly because they are tradition (I think replacing/losing HMs is the equivalent of not choosing your starter) and partly because they add a layer of gameplay to them. I've never had any problem carrying an HM slave around.
But, rock smash and cut could use a bit of a buff.
Forgot about rock smash but I seem to recall gen 5 making it not an HM anymore along with whirlpool, defog, and rock climb.
The biggest problem is that there are 3 HMs that are all water type moves. Condensing them into surf might be a workable solution though and have diving and climbing waterfalls be unlocked from gym badges. Keep waterfall and dive as moves but not require them anymore.
Wall-Mart the place you go when you just got to meat a true moron -Lord of Phendrana Pokemon Black FC = 3396 8733 5419