Well, lemme see....*does mental calculations*
Okay, so going through every generation, the longest it would take to get a type is after you have three badges. This is only the case in Red and Blue, where the first Fighting Type is Machop, obtainable in the Rock Tunnel. You don't have to worry about it as you're using Yellow, where Mankey can be found on Route 22.
As for other instances, most can be found before the first or second badges, with just a small few requiring the two badges(ie. Electrike in RSE, Machop in GSC). So basically just use your starter until you reach this point, wherever that may be.