Let $N$ be an abelian minimal normal subgroup of $G$. Then $N$ has a complement in $G$ iff $N\not\leq \Phi(G)$. Let $N$ be an abelian minimal normal subgroup of a finite group $G$. Then $N$ has a complement in $G$ iff $N\not\leq \Phi(G)$, where $\Phi(G)$ is the Frattini subgrup of $G$.
The Schur-Zasenhaus theorem says that if in addition $(N,G/N)=1$ then $N$ has a complement but I don't think I can use it here.
(a) Let $N\not\leq \Phi(G)$. Then there exists $M$ maximal in $G$ such that $N\not\leq M$ (1). As $M\leq NM$ either $NM=M$ or $NM=G$. If the former then $N\leq M$, absurd. Therefor $G=NM$ (2). Now suppose $M$ normal in $G$. Then $N\cap M$ is an abelian normal subgroup of $G$ and hence $N\cap M=1$ due to the minimality of $N$ and the thesis follows from (2). However $M$ could well be not normal. On the other hand $\Phi(G)$ is not a candidate for the complement because in $D_6=\langle \sigma,\tau\rangle$, $|\sigma|=3$, $\langle\sigma\rangle$ is abelian minimal normal but $\Phi(D_6)=1$.
(b) Let $H$ be a complement of $N$ in $G$. If $H$ maximal in $G$ then as $N\not\leq H$ I have $N\not\leq\Phi(G)$ as desired. But again why is $H$ going to be maximal? Could somebody give me a hint to this problem?
EDIT: From scratch: Let $N\not\leq\Phi(G)$. Then there exists $M$ maximal in $G$ such that $N\not\leq M$ (1). As $G$ finite, it has an abelian minimal normal subgroup $N_1$. What is more $N_1\leq N\cap M$ necessarily. To simplify assume $N_1=N\cap M$. To apply the inductive hypothesis to $M$, whose order is less than $|G|$, I still need to prove $N_1\not\leq\Phi(M)$. Assume $N_1\leq\Phi(M)$. And here I hope a contradiction will arise but can't find it. Can you?
Another thing. The author of this book (Kurzweil and Stellmacher, The theory of finite groups, an introduction, New York, 2004) has just proved two theorems about complements: the Schur-Zassenhaus and the Gaschutz theorems. Could I not use one of them to solve the problem?
If $NA=G$ and $N\cap A=1$ then $NH=G$ for every maximal subgroup $H$ containing $A$. Hence $N\not\subseteq H$ and $N\not\subseteq \Phi(G)$.
Conversely if $N\not\subseteq \Phi(G)$ then $N\not\subseteq H$ for some maximal $H$. Then  $NH=G$. Then $N\cap H\ne N$ is normal in $G$ (because the intersection is normal in $H$ and in $N$ as $N$ is abelian), so this intersection is 1 and $H$ is a complement.
Hi: Let $N\not\leq\Phi(G)$. Then there exists $M$ maximal in $G$ such that $N\not\leq M$ (1). But $M\leq NM$ and therefor either $M=NM$ or $G=NM$. If the former then $N\leq M$ contradicting (1). So $G=NM$ (2).
Let $A=N\cap M$. I'll show $A$ is normal in $G$. Let $a\in A$ and $nm\in G$. Then $b:=(nm)^{-1}anm= m^{-1}am$ (because both $a$ and $n$ are in $N$ which is abelian). But $A$ normal in $M$. So $b\in A$ and $A$ normal in $G$.
That is $A$ is an abelian normal subgroup of $G$ included in $N$ which means either $A=1$ or $A=N$. The latter contradicts (1). So $A=1$ wich together with (2) proves one of the problem statement inferences. How can I prove the other one?