Tanto quanto me lembro, o tipo tem uso corrente menos popular que o gajo, e ambas as expressões têm pelo menos largas dezenas de anos (eu já tenho mais de oitenta, e sempre as ouvi!).
Dado que, segundo o dicionário francês Robert, type no mesmo sentido se usa desde 1881, suponho que esteja na origem de tipo com idêntico significado. Quanto a gajo, é derivado regressivo de gajão, e este (segundo se julga, originado no caló espanhol gachó, «homem») data do século XIX (Filinto Elísio), segundo J. Pedro Machado.