We are all infinitely soluble!

$CH_4$ is insoluble because it is a non-polar compound and there is no possibility of Hydrogen bonding with water molecules.

$He$ is insoluble due to its inertness and absence of polarity because it is monoatomic.

$N_2$ has no polarity so it is not soluble.

$O_2$ also has no polarity but it is very less soluble, usually in $ppm$ but it is considered as insoluble in water.

All other molecules are soluble either due to their reaction with water or due to polarity in them or due to hydrogen bonding.

The main concepts here are that like dissolves like and H-bonding is directly proportional to solubility .

I'd like to point out an exceptional case to the fact that like dissolves like . This hasn't got anything to do with the question.

The exception is that $NH_3$ is polar and $BF_3$ is non-polar. But they are soluble in each other. This is due to the fact that there is an acid-base reaction taking place. $NH_3$ is a lewis base and $BF_3$ is a lewis acid. Since they react with each other, they are said to be soluble in each other given the fact that they are not like molecules(in terms of polarity).