Well, since my idea of not having HMs was rejected, I bring forward the following suggestions in order of preference:For 4, I believe in D/P it is like that.
1. HMs can be used simply by having them in your bag, like in Mystery Dungeon.
2. You can keep 2 extra Pokemon in your party which you can only use for HMs and other field moves, but not battling.
3. At the start of the game, the professor gives you 2 Pokemon which have crappy base stats (to prevent them from being useful for anything else) that can between the two of them learn all the HMs.
4. 2 Pokemon that can learn all the HMs between them, or whose evolutions can learn all the HMs between them, are available near to the start of the game.
Starly can only learn Defog and Fly, though, so for that to work Bidoof would have to learn 6 moves at once. Which it can't. The combinations I was thinking of were more along the lines of Tropius/Marill or Bibarel/Togetic.
Then again, it's a fangame, so why not change around the learnset of some Pokemon to suit our own evil purposes?
EDIT: I theorymon'd a bit, and Tropius wouldn't be that broken early on, so that's one half of a possible combination done (Fly/Cut/Strength/Rock Smash)
FURTHER EDIT: Nothing learns both Dive and Rock Climb except Smeargle which doesn't count... maybe we should change one of those?