I am aware that this is a relatively simple question if you use quotients, because $G/Z(G)$ has order $p$, and hence the quotient is cyclic, and therefore $G$ is abelian, so the center is the whole group, contradiction.
However, I am interested in a proof that does not use quotients, normality, Cauchy, Sylow, or similar tools. I came across one such proof, but I have a question about one particular detail. Here is the relevant part:
Suppose $|Z(G)| = p^{n-1}$. Then $G$ is not abelian. Take an element $x$ that is not in the center, and consider the elements $x, x^2, \ldots ,x^{p-1}$. The claim is now that none of these elements are in the center of $G$. For suppose one of these elements were in the center. Then $x^k \in Z(G)$ for some $k$ such that $2 \leq k \leq p - 1$. Now the center has order $p^{n-1}$, so $(x^k)^{p^{n-1}} = e$, and so $|x|$ divides $p^{n-1}k$ and $|x|$ divides $p^n$. Therefore $k$ must be a power of $\mathbf{p}$.
Why is the part in bold true? Why can't $k$ be any integer between $2$ and $p^{n-1}$?
PS: if you know of another proof that doesn't use any of the weapons mentioned above, please share.
That's not well written; rather, $k$ cannot lie in the required range.
If $1\lt k\leq p-1$, then $\gcd(k,p)=1=\gcd(k,p^n)$, since $p$ is prime. Therefore there exist integers $\alpha$ and $\beta$ such that $1=\alpha k+\beta p^n$.
Now, $$x = x^1 = x^{\alpha k + \beta p^n} = (x^{\alpha k})(x^{\beta p^n}) = (x^k)^{\alpha}(x^{p^n})^{\beta} = (x^k)^{\alpha}e^{\beta} = (x^k)^{\alpha}\in Z(G),$$ since $x^k\in Z(G)$. But this contradicts the choice of $x$. Thus, none of $x$, $x^2,\ldots,x^{p-1}$ lie in $Z(G)$.
From this point, you can complete the proof by noting that $\langle Z(G),x\rangle$ contains at least all elements of the form $zx^i$ with $z\in Z(G)$ and $0\leq i\leq p-1$, and all are distinct (if $zx^i=wx^j$ with $j\geq i$, then $x^{j-i}=w^{-1}z\in Z(G)$, hence $j-i=0$, so $i=j$ and $z=w$). This gives you $|Z(G)|p = p^n$ elements. Thus, $\langle Z(G),x\rangle=G$, but then $G$ is abelian: any element in the generating set commutes with every element in the generating set.
Added. In comments I mention that one can show that the smallest value of $k$ such that $x^k$ lies in $Z(G)$ must be a power of $p$ (without using quotients, of course).
To expand: let $k$ be the smallest positive integer such that $x^k\in Z(G)$. We know that the order of $x$ is a power of $p$, say $p^t$. Let $\gcd(k,p^t)=p^s$. Note that of course $s\leq t$.
Let $\alpha$ and $\beta$ be integers such that $\alpha k + \beta p^t = p^s$. Then $$x^{p^s} = x^{\alpha k + \beta p^t} = (x^k)^{\alpha}(x^{p^t})^{\beta} = (x^k)^{\alpha}\in Z(G),$$ thus, $x^{p^s}\in Z(G)$; as $p^s| k$ and $k$ is the smallest positive integer such that $x^k\in Z(G)$, it follows that $p^s=k$, so the smallest $k\gt 0$ such that $x^k$ that lies in $Z(G)$ is a power of $p$, as claimed.