Here is a construction that allowed me to verify with a few minutes of computer time that such cycles exist for all even $N \leq 10^{12}$. Let $G_n$ be the "prime-sum" graph with vertices labeled $1,\dots,n$ and edges connecting numbers that sum to a prime. First notice that if $N$ is even and there is a twin prime pair $N+2k-1$ and $N+2k+1$ with $2k<N$, then there is a path in $G_N$ from $2k-1$ to $2k$ that includes all larger numbers up to $N$ (just follow the edges that correspond to sums $N+2k-1$ and $N+2k+1$). So if there is a hamilton path in $G_{2k}$ from $2k-1$ to $2k$, then combining these two paths yields a hamilton cycle in $G_N$. 

It is relatively straightforward to construct inductively such hamilton paths for $2k<10^7$, again using twin primes. If $2k-1$ and $2k+1$ are prime, the edges of those two sums immediately yield the desired path (this would give Douglas Zare's construction). Otherwise let $2k+a-1, 2k+a+1$ be the next twin prime pair. The edges corresponding to these two sums will give a path from $2k-1$ to $2k$ leaving out only the numbers $1,\dots, a$. Assuming that we already obtained a hamilton path from $a-1$ to $a$ in $G_a$, we can now "glue" that path to the path from $2k-1$ to $2k$ by replacing an appropriate edge. Alternatively we can use the hamilton path from $a+1$ to $a+2$ in $G_{a+2}$ and "glue" with two suitably chosen edges.  

This means that whenever $N$ is even and there is a twin prime pair larger than $N$ and within distance $10^7$, there is a hamilton cycle in $G_N$. We can therefore check the existence of such hamilton cycles for  $N\leq 10^{12}$ (and probably way larger) by finding a sequence of twin prime pairs with distances just below $10^7$, without performing any calculations for individual values of $N$.