There could be multiple reasons of how they started their journey but only GameFreak knows the real answer.
1: Somebody gave them their Pokemon.
This happens often in the Pokemon universe, the Professor gives you your starter. Some person gives you an egg. Some other way you get Pokemon from people.
2: Their Pokemon could have joined them.
This happens sometimes in the anime, a trainer befriends a Pokemon, it allows itself to be caught, now the trainer can catch more Pokemon because of the Pokemon that they have befriended.
3: They caught their Pokemon without using another Pokemon.
Yes, it is highly unlikely but it could happen.
Hope I helped!