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.
Let $a_1, \dotsc, a_6$ be the number of vertices of the components.
We know that $a_i \geq 1$ and $\sum a_i = 25$.
To find the minimum number of edges of $G$, let's first look at a single connected component. A component with $n$ vertices cannot have less than $n-1$ edges. Also, a star graph is connected and have exactly $n-1$ edges, so we can attain this minimum.
Thus, the minimum number of edges in $G$ will be:
$$ \sum_{i=1}^6 (a_i - 1) = \sum_{i=1}^6a_i - 6 = 25 - 6 = 19 $$
The maximum can be found in a similar way. The maximum number of edges in a component with $n$ vertices is $\binom{n}{2}$, that is attained on a complete graph $K_n$. Thus we want to maximize:
$$ \sum_{i=1}^6\binom{a_i}{2} = \sum_{i=1}^6 \frac{a_i(a_i-1)}{2} = \frac{1}{2} \left( \sum_{i=1}^6 a_i^2 - \sum_{i=1}^6a_i \right)$$
$$ = \frac{1}{2} \left( \sum_{i=1}^6 a_i^2 - 25 \right)$$
Note that $\sum_{i=1}^6a_i^2$ is convex, so the maximum is attained on the boundary of the region given by $\sum_{i=1}^6a_i = 25$, so we have a maximum when $a_1 = 1$, $a_2 = 1$, $a_3 = 1$, $a_4 = 1$, $a_5 = 1$ and $a_6 = 20$. Hence the maximum number of edges is:
$$ \frac{1}{2} \left( 20^2 + 5 - 25 \right) = 190$$
That is attained when the components are five copies of $K_1$ and one $K_{20}$.
Best Answer
Apparently, we still need to prove that there cannot be $17$ edges or more under the given conditions. In fact, if our graph has at least $17$ edges, then removal of two vertices of degree $3$ will lead to removal of no more than $6$ edges. But then we would get a graph with $5$ vertices and at least $11$ edges, which is impossible.
Graph $K_{3,4}$ has $12$ edges and $4$ vertices of degree $3$. If a graph has $7$ vertices and $13$ edges, then it cannot be bipartite. This can be easily checked because graphs $K_{1,6}$ and $K_{2,5}$ have $6$ and $10$ edges respectively and it is obvious that any bipartite graph is complemented to a complete bipartite graph with the same number of vertices.