The reason is that each carbon atom in CFCs are surrounded by single co-valent bonds with the halogens. As a result CFCs contain strong carbon-carbon single bonds and strong carbon-halogen bonds.
The carbon-halogen bonds are only very slightly polar and so there aren't any bits of the molecules which carry any significant amount of positive or negative charge which other things might be attracted to.
There isn't much electronegativity difference between carbon and chlorine, and not much between fluorine and carbon either, so there is hardly any bond polarity. Plus, a totally symmetrical CFC molecule such as 1,2-chloro-1,2-fluroethane would be completely non-polar.
Since there is a lack of strong electronegativity difference, the only forces acting between each molecule are Van der Vaal's forces.
When a molecular substance dissolves in water, you have to break the intermolecular forces within the substance. In the case of the alkanes, these are Van der Waals dispersion forces amd break the intermolecular forces in the water so that the substance can fit between the water molecules. In water the main intermolecular attractions are hydrogen bonds.
To break these forces, it costs energy, although the amount of energy to break the Van der Waals dispersion forces in something like CFC-11 is pretty negligible.
That isn't true of the hydrogen bonds in water, though.
The only new attractions between a CFC and water molecules are Van der Waals.
These don't release anything like enough energy to compensate for what you need to break the hydrogen bonds in water. Thus the CFC will not dissolve.
You are completely correct in saying that certain CFCs are slightly polar, however, these are almost neglible when attempting to dissolve them in water.
You mentioned putting methane into the troposphere, and I see some major problems with that. The production costs of methane are relatively high, and attempting to deliever the methane payload directly into the lower statosphere poses enormous problems.
Such as costs. No such method is currently available to deliver the many millions of tonnes of methane that maybe required to counter the current levers of the CFCs, not to mention the extra pollution through the use of transport fuel, and the highly flammable nature of methane.
Methane, unlike CFC's are not as stable in the upper atmospheres and readily react with UV and other organic molecules to form other compounds such as carbon dioxide. Hence, there is no guarantee that all of the methane will react with the Cl- radicals ~ more in the range of 1% to 2%.
So, yeah, i have finished ranting