Yah. That is a pain. As a none breather just make sure to get SM tech and blow all the Gas Giants into nothingness and then remake until you get rock or ice.
Or alternatly get yourself a nice slave race that breathes something else and set them up on all the Gas Giants. Otherwise you lose some major production potential.