As Michael Klug points out in the comments, I've thought about related questions before. I'll make a few comments on the question.
Firstly, the usual reduction allows one to consider triangulations on a surface: if a graph $G$ does not induce a triangulation of $\Sigma$, then we can complete it to a triangulation $G'$ so that if $G'$ (or a cover $\hat{G'}$ induced by a cover $\hat{\Sigma}$) is 4-colorable then so is $G$ (or $\hat{G}$).
So let's assume that $G$ induces a triangulation of $\Sigma$. Then the dual graph $G^*$ (with respect to the embedding in $\Sigma$) is a cubic graph. If $G^*$ is 3 edge-colorable (i.e. has a Tait coloring), then one can see that a $\mathbb{Z}/2\times \mathbb{Z}/2$-cover $\hat{\Sigma}\to \Sigma$ will give a lift of $G$ which is 4-colorable. To prove this, identify the three colors with the non-zero elements of the Klein 4-group $V=\mathbb{Z}/2\times \mathbb{Z}/2$. Then coloring the vertices of $G$ corresponds to coloring the faces of $G^* \subset \Sigma$. If we color one face of $G^*$ by $0\in V$, then each time we cross an edge of $G$, we change the color by adding the element of $V$ corresponding to the edge coloring. This is locally well-defined near a vertex, but globally might have holonomy in $V$. So passing to a 4-fold cover $\hat{\Sigma}\to \Sigma$ induced by this holonomy, we get a pulled-back graph $\hat{G}$ which is 4-colorable. (In the planar case, there is no holonomy, and hence Tait's observation that Tait colorings suffice).
Thus it suffices to consider 3-edge colorings of cubic graphs in $\Sigma$. The Snark theorem implies that if the graph $G^*$ is not 3-edge colorable, then there is a Petersen minor (that is, a copy of the Petersen graph embedded topologically in $G^*$). The Petersen graph is non-planar, so must be embedded in an essential way in $\Sigma$ (not isotopic into a disk). Hence any Petersen subgraph of $G^*$ will not lift to some 2-fold cover of $\Sigma$. However, passing to a cover to which no Petersen subgraph lifts, there may be new Petersen subgraphs of $\hat{G^*}$ created. Nevertheless, one can ask if there is a finite cover $\hat{\Sigma}\to \Sigma$ such that the preimage of any embedded cubic graph in $\Sigma$ is not a Snark? Seems implausible, but it is a natural question to ask when thinking about virtual Tait coloring.
One can weaken the condition of Tait coloring, allowing passage to a finite-sheeted cover. If a cubic graph $G^*$ has a perfect matching (also called a 1-factor, a degree 1 regular subgraph spanning the vertices), then the complementary subgraph is a 2-factor, i.e. a regular subgraph of degree 2 containing every vertex, homeomorphic to a union of circles, each component a cycle graph . If the 2-factor is also bipartite (2-colorable, r every component has an even number of edges), then we may 2-color the 2-factor and use a third color for the 1-factor to get a Tait coloring of $G^*$. Then we can look for a 2-factor $C\subset G^* \subset \Sigma$ such that every non-bipartite component of $C$ is a non-trivial curve on $\Sigma$. In this case, we can pass to a $2^{2g}$-fold cover in which ever non-separating curve has each component of the preimage an even-index cover, and every separating essential curve has preimage components non-separating, and repeat, to get a finite cover for which the preimage of every essential curve is an even index cover on each component. Then the preimage of a 2-factor with the above properties will be a bipartite 2-factor, and hence the preimage graph will be 3-colorable (and a further 4-fold cover will give a 4-colorable dual triangulation).
One knows that every bridgeless cubic graph has a perfect matching (or 1-factor, and hence a 2-factor), known as Petersen's theorem. One could try to modify the proof to try to show that a graph $G^*\subset \Sigma$ has a 2-factor with odd cycles all essential. But I didn't see how to do this. In any case, it seems possibly easier to find a controlled cover of $\Sigma$ where the preimage of every cubic graph has a 2-factor with essential odd cycles.
Another special case is triangulations of even degree. Then we can try to 3-color the vertices. Once one 3-colors the vertices of a triangle, there is a unique way to continue the coloring, well-definied locally around a vertex because of the even degree hypothesis. This may have non-trivial holonomy, but passing to an $S_3$-cover (of index 6), we get a preimage which is a 3-colorable graph. This works e.g. for $K_7\subset T^2$.
Ultimately, this problem ought to be as hard as the 4-color theorem itself. Given a large graph embedded in a disk, one ought to be able to insert it into a disk on a surface $\Sigma$ of genus $>0$ as a subgraph. Coloring the graph larger graph in a finite-sheeted cover will induce a coloring of the planar graph. So I think one will likely have to use the 4-color theorem or parts of its proof as an essential ingredient in resolving this question.
One reduction I've contemplated is to make the surace the boundary of a handlebody, and pass to the universal cover of the handlebody. The preimage of the boundary is a planar surface, so the preimage of the graph $\tilde{G}$ is 4-colorable. The
space of 4-colorings of $\tilde{G}$ is a closed subset of the Cantor set $4^\tilde{V}$, where $\tilde{V}$ is the vertex set of $\tilde{G}$. The covering translations form a rank $g$ free group. If there is a probability measure on the space of colorings which is invariant under the free group action, then I can show that there is a finite-sheeted cover (induced by a cover of the handlebody) which is 4-colorable, using a theorem of Lewis Bowen. However, I haven't been able to show the existence of such a probability measure (again, this may require non-trivial input from the proof of the 4-color theorem). One could do a similar thing with 2-factors of cubic graphs, where every contractible cycle is bipartite, and ask for an invariant probability measure on these. This approach, if it worked, would likely not give a uniform finite-sheeted cover.
