I disagree with the notion that the graph has to be imbedded in the plane for this problem to make sense. It merely needs to be imbedded in a compact surface, and since all finite graphs have the property that they can be imbedded in a surface, then the result should hold for all finite graphs (since it is indeed $2E$). it is also clear that each edge will not generally be counted once per face. An acyclic graph for instance only has one face. and a traversal of the boundary requires you to walk each edge twice.
1 Every surface has a triangulation. This is hard to prove, but it comes from a topological result on the classification of surfaces.
2 Your graph is homomorphic to a subgraph of some triangulation. I do not remember what this theorem is called.
3 a triangulation quite easily has this property. It falls right out of the definition, in that every edge shares precisely two faces.
4 removing an edge common to two faces causes all other edges common to them to be double counted in the traversal of the boundary.
5 subdividing/unsubdividing an edge does not change.
Your graph has this property.
This is probably not the best way to solve this problem. but it uses a nice definition of face. I also didn't work through 4 and 5. because I couldn't think of a way to do them nicely, and I figured you only wanted help coming up with a proper strategy.