You can catch Vulpix (Growlithe in HG) pretty early on... and Magmar not too long after. Trying to recall if there are any other fire Pokemon pre-E4. I know Houndour's not until Kanto.
...But Vulpix/Growlithe and Magmar makes HGSS pretty abundant with fire-types compared to most games.
There's also the Slugma egg from Primo in Violet City, and you can get the Fire Stone for Flareon as soon as you unlock the Pokéathlon. And finally, Ponyta can be caught just before Victory Road.
This link will take you to the code generator for the Slugma, among other minor rewards. Just put in your in-game Trainer ID, the game you're playing, and the game's language, and you're good to go. So including Cyndaquil, there are six fire-types in the Johto remakes pre-E4. Not bad.