Let's first formulate Pavel's idea in terms of the Bondy–Chvátal theorem instead of Ore's Theorem.
The theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian, where the closure is defined as the unique graph resulting from successively adding edges between any pair $u,v$ of vertices with $d(u)+d(v)\ge n$.
So a non-Hamiltonian graph with maximal number of edges must have $d(u)+d(v)\lt n$ for all missing edges, since otherwise its closure would be a different non-Hamiltonian graph with more edges. Thus, two vertices $u,v$ not connected by an edge only have $d(u)+d(v)\lt n$ instead of the maximum possible $2n-3$ incident edges, so at least $2n-3-(n-1)=n-2$ edges are missing. Thus the graph has at most $\binom n2-(n-2)=\binom{n-1}2+1$ edges.
Moving on now to your problem of finding the maximal number of edges of a non-Hamiltonian graph on $n$ vertices with minimal degree $2$, let's look for two missing edges with no vertices in common. A moment's reflection shows that if all pairs of missing edges have at least one vertex in common, that means that either there is only a single triangle of missing edges, in which case the graph is Hamiltonian, or all missing edges have the same vertex in common, in which case the graph is also Hamiltonian since the common vertex has at least two edges connecting it to the remaining complete graph.
Thus, since the graph is non-Hamiltonian, there exists a vertex-disjoint pair of missing edges. The four vertices involved could have a maximum of $4(n-1)-\binom42=4n-10$ incident edges, but by the Bondy–Chvátal theorem they in fact have at most $2(n-1)=2n-2$ incident edges, so at least $2n-8$ edges are missing. That gets us almost all the way, since $\binom n2-(2n-8)=\binom{n-2}2+5$.
Narrowing the gap from the other side, we find that we can actually improve your construction by one edge by connecting the two lone vertices not among themselves, but separately to the same two vertices of $K_{n-2}$. They are still both missing $n-3$ edges, but now one of these is double-counted, so this graph has $\binom{n-2}2+4$ edges and is not Hamiltonian for $n\gt4$.
Now it remains only to deal with the case of $\binom{n-2}2+5$ edges, corresponding to $2n-8$ missing edges. Since the edges among the four vertices are double-counted in the application of the theorem, there can be no such edges. Thus we can apply the theorem to all six pairs of the four vertices. Applying it to the pair with the two lowest degrees shows that they must all have exactly degree $(n-1)/2$. For sufficient $n$, that means that they're connected to the remaining $K_{n-4}$ by enough edges to allow for a Hamiltonian cycle. One might have to do some slightly tedious casework in order to exclude special cases for small $n$.
To summarize, for sufficiently large $n$ ($n\gt16$ will do), the maximal number of edges in a non-Hamiltonian graph with minimal degree $2$ is $\binom{n-2}2+4$, and this bound is attainable by an explicit construction.
P.S.: There is in fact a special case with $n=7$: Connect each of the four lone vertices to all vertices of $K_3$. That makes for a total of $15=\binom{7-2}2+5$ edges; the minimum degree is $3$; and the graph is not Hamiltonian, since the three vertices of $K_3$ can be used to reach at most three of the four lone vertices. That leaves the question open whether the maximum for $n=9,11,13,15$ is $\binom{n-2}2+4$ or $\binom{n-2}2+5$.
P.P.S.: An analogous construction yields another special case with $n=9$: Connect each of the four lone vertices to the same four vertices of $K_5$. The cross-edges are still not enough to allow for a Hamiltonian cycle. I suspect that this is the last exception, since an analogous construction for $n=11$ (connecting all four lone vertices to the same five vertices of $K_7$) fails and allows for a Hamiltonian cycle.
Best Answer
Found a lot easier proof for the harder part, using Ore's theorem: If $G$ is complete, there's a Hamiltonian cycle. So suppose it's not. We'll take some non-neighbor vertices $v,w$, and delete them from the graph. For the resulting graph $G'$ - $|E(G')| \geq \binom {n-1}{2} + 2 - (d(v)+d(w))$. In the complete graph on $n-2$ vertices there are $\binom {n-2}{2}$ edges. So, lastly, we get that $$\binom{n-2}{2} \geq \binom{n-1}{2} + 2 - (d(v)+d(w))$$ and after some easy operations, we get that $$d(v)+d(w) \geq n$$ which is exactly Ore's condition for a Hamiltonian graph to exist.