As Michael Klug points out in the comments, I've [thought about][1] 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][2]), 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][3] $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][4] 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-set*,  a degree 1 regular subgraph spanning the vertices), then the complementary subgraph is a 2-set, i.e. a regular subgraph of degree 2 containing every vertex, homeomorphic to a union of circles, each component a [cycle graph][5] (I learned this terminology from [this paper][6]). If the 2-set is also bipartite (2-colorable, or every component has an even number of edges), then we may 2-color the 2-set and use a third color for the 1-set to get a Tait coloring of $G^*$. Then we can look for a 2-set $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-set with the above properties will be a bipartite 2-set, 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-set, and hence a 2-set), known as [Petersen's theorem.][7] One could try to modify the proof to try to show that a graph $G^*\subset \Sigma$ has a 2-set 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-set 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$. 


  [1]: https://mathoverflow.net/a/249576/1345
  [2]: https://en.wikipedia.org/wiki/Edge_coloring#Regular_graphs
  [3]: https://en.wikipedia.org/wiki/Klein_four-group
  [4]: https://en.wikipedia.org/wiki/Snark_(graph_theory)#Snark_theorem
  [5]: https://en.wikipedia.org/wiki/Cycle_graph
  [6]: https://arxiv.org/abs/1710.05002
  [7]: https://en.wikipedia.org/wiki/Petersen%27s_theorem