I forget which one, but there is a race that can make class 4 planets out of class 0 planets.
I'm afraid this is not true. It is not possible to colonize a PQ0 planet (no AI + player are able to do so), furthermore, all AI are coded to ignore all PQ1 planets as well (as they wouldn't have any starports without terraforming)
The only thing that can change PQ0 to something higher is a galactic event.
Gormo, it might be bad luck that you had with the map generation, and also, the AI on higher difficulty settings will develop his game pretty fast.