The degree sequence $\langle 3,3,2,2,2,2\rangle$ will work:
*——*——* * *
| | | |\ /|
*——*——* | *——* |
|/ \|
* *
Suppose $G$ is planar $4$-connected, and let $u,v$ be any two vertices of $G$. We choose a face $C$ containing $v$ and an edge $e$ of $C$, then apply the theorem to find a $v,u$-path $P$ containing $e$.
We'd like to make sure that $P$ contains at least $4$ vertices. To accomplish this, we choose $C$ and $e$ carefully: we want to make sure that neither $u$ nor $v$ is an endpoint of $C$.
Let $x,y$ be two neighbors of $v$. Since $G$ is $4$-connected, there is an $x,y$-path in $G-\{u,v\}$, which forms a cycle $D$ together with the edges $vx$ and $yv$. In a planar embedding of $G$, $D$ divides the plane in two regions, one of which does not contain $u$. Let $C$ be a face containing $v$ which is inside the region not containing $u$. Then $C$ has at least two vertices other than $v$, and so we can choose an edge in $C$ whose endpoints are distinct from $u$ and $v$.
(Maybe there was a more elegant way to do this step.)
Now $P$ contains at least $4$ vertices: $u$, $v$, and the endpoints of $e$. I claim that $P$ must be a Hamiltonian path.
If not - if there is a vertex $z$ not in $P$ - let $F$ be the $P$-component containing $z$. Deleting the vertices of attachment of $F$ disconnects $z$ from the remaining vertices of $P$ (there are at most $3$ vertices of attachment, but at least $4$ vertices in $P$). This means that $G$ is at most $3$-connected, violating the hypothesis.
Best Answer
If trying small examples doesn't work (and it doesn't, because very small examples don't exist), your next step should be trying out slightly larger examples with software.
Go to Brendan McKay's graphs page and you'll be able to download a
.g6file of all the connected $9$-vertex planar graphs. (With $8$ or fewer, this won't work.)From here, pick out the ones with $21$ edges, and from there the Hamiltonian ones. Finding the degree sequence along each Hamiltonian cycle of each graph that's left results in some overlap; for example, there are two graphs with the ordered degree sequence $5, 5, 5, 3, 6, 3, 6, 3, 6$.
Here are these two planar graphs, with the corresponding Hamiltonian cycles $(a,b,c,d,e,f,g,h,i,a)$ highlighted. One quick way to see that these are not isomorphic is that in the first graph, any two vertices of degree $3$ have a common neighbor; in the second graph, $d$ has neighbors $\{b,c,e\}$ but $h$ has neighbors $\{a,g,i\}$.