Here are some remarks, which don't directly answer the question of how to exhibit your counter-example on paper, but rather suggest some ways of thinking about your question, and your solution.
When reading the title of this question, but before reading the body of the post, I thought that this statement couldn't be true. My reasoning was as follows:
given an odd integer $N$, there are only $[\sqrt{N/2}]$ numbers such that $2x^2 \leq N,$ and to write $N = 2 x^2 + \text{ prime },$ for one of these $[\sqrt{N}/2]$ numbers $x$ we would need $N - 2 x^2$ to be prime.
By the prime number theorem, we know that the primes from $2$ to $N$ are themelves spread fairly thinly; roughly $1/\log N$ of them is prime. So it just doesn't seem very likely that the $[\sqrt{N}/2]$ values $N - 2 x^2$ should always have to meet the roughly $N/\log N$ primes between $2$ and $N$ (where by always I mean for every value of $N$).
You might like to compare with the Goldbach conjecture: it is expected to be true that any even $N$ can be written as the sum of two primes, and a heuristic argument in favour of Goldbach is given here; if you compare it with your question, you can note that the probability of a number being twice a square is much smaller than the probability that it is a prime (roughly $1/\sqrt{x}$ vs. $1/\log x$), and so the heuristic argument given there, adapted to your question, would suggest that it should be false.
Once you suspect an answer to a question like this should be false, there are at least two possibilities: try to refine the heuristic argument to estimate the likely size of the first counter-example, or simply start computing to find a counter-example. Unless the first option is completely straightforward, it makes sense to pursue the second option first; only if it doesn't produce the desired counterexample after some time would it make sense to return to the heurstic argument and investigate it more carefullly. I imagine that in your case it didn't take long to find that $5777$ was a counter-example, and (as I've already written) finding it by computer search makes perfect sense as an approach.
Added: See the comments to Gerry Myerson's answer for a more careful discussion of the above heuristic argument, which suggests that if $N$ is large enough then it should be possible to write $N =$ prime $+ 2 x^2$. (The point being that $(1 - 1/\log N)^{\sqrt{N/2}}$ tends to $0$ as $N$ gets large.)