According to this abstract from a paper titled "Why Is It Much Easier To Nucleate Gas Bubbles than Theory Predicts?":
Bubble nucleation from supersaturated gas solutions generally takes
place at much lower supersaturations than are expected from the
theory. Furthermore, the same theory predicts that the threshold
concentration of gas needed to cause nucleation should be essentially
independent of the gas species used, a finding contradicted by
experiment. There are two general explanations: first, that the
theory is wrong, or second, that there is a previously unidentified
factor which is influencing the results of the experiments. Given the
success of the fundamental theory in other areas, the second
explanation is preferred. The previously unrecognized factor is
identified here as being the surface activity of the gases which form
Although this is discussing conditions of low supersaturation and not subsaturation, I assume the same concepts apply, though it would cost me $40 to get the full article text and find out for sure.
I'm pretty sure what's happening here is that through the random motion of dissolved gas molecules, occasionally enough of them adhere to one another to form the nucleus of a bubble. Particularly at very small radii, the high surface tension of water dominates otherwise destructive forces, and a micro-bubble begins to form. But by the definition of saturation with respect to bubble formation, it would seem that you cannot have "macro-scale" bubble formation and growth persisting under conditions of subsaturation as equilibrium is reached.
If I can paraphrase your question as:
"If I lower the gas pressure to below its saturation pressure, does
the gas come out of solution if there are no interfaces (nuclei) for
bubbles to form?"
then the answer is yes, regardless of the presence or absence of bubbles. The dissolved gas molecules will partition at the gas-liquid interface until equilibrium concentrations are achieved in each phase. If some gas bubble began to form, it would quickly redissolve under conditions of subsaturation with respect to the gas solubility.
Unless I'm missing something about the importance of bubbles in your question, this would pretty clearly be the bottom line answer. Please comment if I've missed the crux of your question.