Here's a lemma without proof: Let $G$ be simple with no degree-$2$ vertices and no cut vertices. Then either $G$ is a cycle graph or $G$ has an edge $(v_1, v_2)$ such that its deletion still leaves a graph with no cut vertices. Note that this edge is the chord of a cycle in $G$.
We are done if $G$ is just a cycle, so suppose it is not. Our goal is to find two adjacent vertices that both have degree $2$. By deleting them, you reduce the number of vertices by $2$ and the number of edges by $3$, so you win by induction. Suppose by way of contradiction that there is no such pair of vertices.
First suppose that $G$ has no cut vertex. Let $G'$ be the cosimplification of $G$, that is, the graph obtained by identifying every pair of edges joined by a degree-$2$ vertex. There is an edge $(v_1, v_2)$ that forms a chord of a cycle on $G'$. In $G$, this edge must be subdivided to make a path $P$, and it must be subdivided only once or else we have adjacent degree-$2$ vertices, so $|P| = 2$. Let $C'_1$ and $C'_2$ be cycles of $G'$ that only intersect at $(v_1, v_2)$ (their existence is implied by the lemma), and let $C_1$ and $C_2$ be their corresponding cycles in $G$. Then the disjoint union of $C_1$ and $C_2$ is a cycle in $G$, but it has length
$$0 - 2|P| \equiv 2 \pmod 3$$
which contradicts every cycle having $0 \pmod 3$ edges.
If $G$ has a cut vertex, then choose one such that the deletion separates the graph into parts $K$ and $J$ such that there are no edges between $K$ and $J$, and the order of $K$ is minimal. (In particular, there are no cut vertices within $K$). Then the same argument by contradiction above shows that there must be two degree-$2$ vertices adjacent to each other within $K$.