The sum does not vanish when $N$ is odd. I will use a variant of François Brunault's idea.

Let us assume that $N$ is odd. Applying the Galois automorphism $\mathbb{Q}(z)\to\mathbb{Q}(z)$ induced by $z\mapsto z^2$, the sum becomes
$$S:=\sum_{k=0}^{N-1}e^{2\pi i(2k^2+k)/N}.$$
Hence it suffices to show that $S\neq 0$. Let us write
$$w:=1+i,\qquad f(z):=e^{2\pi i(2z^2+z)/N}.$$ We shall integrate on translates of the slanted line $w\mathbb{R}$, upwards. An application of the residue theorem shows that
$$S=\int_{-1/2+w\mathbb{R}}\frac{f(z+n)-f(z)}{e^{2\pi i z}-1}\,dz=
\int_{-1/2+w\mathbb{R}}f(z)\,(1+e^{2\pi z}+e^{4\pi z}+e^{6\pi z})\,dz.$$
In the last integral, we can shift the contour to $w\mathbb{R}$, and then after writing $z=wt$ (where $t$ increases from $-\infty$ to $\infty$), it is straightforward to evaluate the four pieces coming from $1$, $e^{2\pi z}$, $e^{4\pi z}$, $e^{6\pi z}$. The final result is
$$S=\exp\left(\frac{\pi i}{4}-\frac{\pi i}{4n}\right)\sqrt{n}.$$
This is clearly nonzero, hence the claim is proved.