Personally what I'd want to fix it would be for a broad category of moves to act as a Hidden Move... so the Cut category could be fulfilled by Slash, Leaf Blade, Night Slash, and so forth. Strength could be fulfilled by many fighting moves or even Psychic to lift them out of the way.
Apparently a surfboard was programmed into one of the earlier pokemon games but was never accessible... I wish HM key items were in the newer games though. :(