I've had something exactly like this implemented in my hack for quite some time, where if a Pokemon is capable of learning a HM, it can use it in the field. I just did it the lazy way and scripted cut trees/rock smash rocks/surf script/etc. to check your party for a list of pokemon compatible with the moves. It will prefer Pokemon that know the move before choosing one that doesn't but can learn. It's inelegant, and lazy, but it works and is indistinguishable graphically from using HM moves in the field normally. I haven't come up with a solution for Fly, and since I'm on the fence about including it as a field move, I've not really tried. Ideally, the option for Fly in the party menu would appear after obtaining the badge and its HM, as that would be conceivably the earliest the player would be able to use it if they're not trading. But, that begs the question, do teleport and dig get the same treatment? Would having them available at no cost with a Pokemon that can learn it in your party make the game too easy?
EDIT: I suppose if you were really lazy, you could have the person that gives you Fly give you a Flight Map key item, or something, that checks the party for a Pokemon capable of using Fly before callasm-ing the flight map and letting you select a location.
