The wiki doesn’t have a page for what badges let you use what HM moves out of battle. All it does is list substitutions for HM moves.
You should be able to use it either right off the bat, or after Gym 1. I know I used it immediately after beating the first gym, but I don’t if you can use it earlier.
not sure about when, but there’s some moves ik that work. i used headbutt on my cubone in the eaely game, and heavy slam on my d. haxorus in the late game