The problem is that "normal ordering" is not defined on operators but on "symbols". Within the normal ordering $::$ all symbols commute and hence the second part of your proof is not valid.
See the following Physics.SE question and its answers: How exactly is "normal-ordering an operator" defined?
Wick's theorem applies to free fields, so how can it be used in interacting theories? The solution is the interaction picture.
Wick's theorem is about time-ordered products of Heisenberg picture operators in a free field theory. In the interaction picture, you write your Hamiltonian as a free part plus a small perturbation for the interactions: $H = H_0 + ...