First generation stars didn't do the CNO cycle initally.
It is estimated, that after the Big Bang three quarters of the matter is hydogren, one quarter helium, and trace amounts of heavier elements. This is then also the composition of (as of now unobserved) first generation stars, having zero metallicity. Even though those stars probably were very massive, they could not run the CNO cycle initially.
Luckily, the CNO cycle is not the only nuclear fusion process in stars. In the proton-proton chain reaction, hydrogen is fused into helium. The star is in equilibrium until the hydrogen in the core is "used up". Then it may collapse and heat until the triple-alpha process begins to produce carbon. From there on there are more and more processes producing many different elements. Due to convection and shell-burning, the CNO cycle might have been running in those first generation stars at later stages.
Interestingly, the most massive of the first generation (population III) stars may have ended up as black holes, gobbling up all of the produced metals (elements heavier than helium). Many others may have exploded in pair-instability supernovae ejecting all material into interstellar space, leaving no compact remnant behind.
A Heger and S. E. Woosley: The Nucleosynthesis Signature of Population III