Paper p.9 and Wikipedia relate the Tutte polynomial of a graph to another polynomial.
If $(x-1)(y-1)=z$, $$T(G;x,y)=F_G(z,y)/H(G)$$
Where $F_G(z,y)=\sum_{A \subseteq E}z^{c(G_A)}(y-1)^{|A|} $ where $c(G)$ is the number of connected components and $H(G)$ has simple closed form. $F_G(z,2)$ is polynomial in $z$ and the coefficient of $C$ of $z$ is the number of connected spanning subgraphs of $G$. The constant coefficient of $F_G(z,2)$ is zero.
So $$F_G(z,2) \mod z^2= Cz=T(G;z+1,2) H(G) \mod z^2 \qquad (1)$$
If $G$ is planar, $T(G;x,y)$ is efficiently computable for $z=2$ which gives the RHS of (1).
Setting $z=2$ we get: $2C \mod 4 =2 T(G,3,2)=\rm{known}$, which allows finding $C \mod 2$.
Will this approach work?
I reproduce the polynomial relation in sagemath after help on MSE.
