for the main game I just put the moves on what ever pokemon I had that could use what I needed there is always the move deleter and relearner heart scales are easy to come by and the moves you need are not horrible.
**spoiler**(post game info)
I use Tropious with
fly (first move so easy to get to)
flash (not an hm but useful)
Strength
Cut
I team it with Carracosta
Dig (if I can't fly will take me where I can)
Surf
Waterfall
Dive
you can catch Tropious on route 18 15% encounter rate
Carracosta is from the Cover Fossil when a fosil is offered to you in the relic castle