Ive found more than one HM slave, since you can only have four moves on a Pokemon. EVs, Items and Nature is not needed since this is ingame.
Sea/Cave HM Slave
IMO Sharpedo is really good.
Sharpedo @Whatever
Ability: Who cares?
EVs: Anything/You/Want
Nature: Don't need to know
Moves:
-Surf
-Waterfall
-Dive/Some attacking move you want
-Strength/Rock Smash
Surf is necessary to reach bases that require crossing water to get it. Waterfall can get you to hidden places. Dive is not important for base hunting, but for a regular HM slave would be good. Replace it with a random attacking move if you don't want it. Strength and rock smash can be useful in caves. Easy to find, on routes 118 and 119 you can get by fishing. I think this one will be useful for bases. Fastest surfer is an added bonus.
But if you want something for just about everything...
Lati@s @Something
Ability: Idk
EVs: It/Won't/Matter
Nature: Not important
Moves:
-Cut
-Fly
-Waterfall
-Surf
Can be used for almost anything except for caves.
If you don't want a legendary...
Crawdaunt@An item
Ability: An ability
EVs: Some/Random/EVs
Nature: A nature
Moves:
-Cut
-Surf
-Strength
-Rock Smash/Dive/Waterfall
Last moves aren't as important. You can have anything but fly
I show all the pokémon who are good, but some other good ones that can be gotten by trade are Froakie, Biberal and Dragonite.
Source