In Fire Red and Leaf Green you get the chance to get two HMs in the same location if you are persistent. When you go to Fuchsia City, you will find an old man in one of the homes next to the Pokemon Center. He's the Warden of the Safari Zone, only problem is he CAN'T talk, so all you get from him are non-sense mumbles. You can't miss the house because it is the only one that has a boulder inside and a mumbling old man.
Now go north, try to make use of HM01 and cut all the trees you need to, because the Safari Zone entrance is nearby. You might require a few tries, it is best when you ignore Pokemon catching for now, remember the only rare Pokemon here are: Tauros, Chansey and Dratini. So unless you actually encounter them I'd say come back for the rest later. Keep going, not only you will find the Safari Warden's gold tooth, but you may be able to find the hidden house with HM Surf.
You should take the tooth with you and bring it to the old man. He will reward you with Strength. Now if you have beaten the gym leader there, you'll be able to use Surf from the hidden house in the Safari Zone all the way past where you found the tooth. Surf is way cooler that Strength!