Suppose we have a finite group $G$ which contains a normal subgroup $M$. Consider the following subgroups of $G$: $C, Q_1, \ldots, Q_{|M|}$, all of which are different complements of $M$ in $G$ (that is, they intersect $M$ trivially and $CM = Q_iM = G$ for all $i$).
I also know that $MC \cong M \times C$, that all of the $Q_i$ are conjugate by an element of $M$ (so every $Q_i$ is self-normalizing), that $C$ intersects trivially all of the $Q_i$'s and that $M$ is complete (that is, centerless and $\operatorname{Aut}(M) = \operatorname{Inn}(M) \cong M$).
I am trying to find a contradiction. As there are as many $Q_i$'s as there are automorphisms of $M$ I am tempted to deduce that some $Q_i$ must act trivially on $M$, and so intersect $C$, but I don't know if this is true.
The situation that you describe is possible. Let $M = C$ be a complete simple group, such as the Mathieu group $M_{11}$. Then the $Q_i$ are the diagonal subgroups $\{ (g,\alpha(g)) : g \in M \}$ for automorphisms $\alpha$ of $M$.