Suppose $p$ is odd. Consider the kernel of $\phi$ in the second fact. It consists exactly of the elements of order dividing $p$, and so there are either $p^2$ or $p^3$ of these; always more than $p$. However, by the first fact, there are exactly $p$ central elements of order dividing $p$. In particular, for every odd prime $p$ and non-abelian $p$-group $G$, there is a non-central element of order $p$, and the subgroup it generates is not normal (since it is order $p$ and not central by assumption).
Suppose $p=2$. Then there are two very explicit cases, $D_8$ which doesn't work, and $Q_8$ which does.
Groups like this, in which every element of order $p$ are central, have been studied by JG Thompson and others. Maps like $\phi$ always exist, and serve to build the upper exponent-$p$ series of the group. In particular, if $Z(G)$ is cyclic, $p$ is odd, and every element of order $p$ is central, then $G$ itself is cyclic. If $Z(G)$ has rank 2, then the “socle series” of $G$ has factors of rank at most 2.