2 color theorem

I assume that during the drawing process you do not allow retracing of part of a line that's already been drawn. If you do then there is a counterexample.

If you don't allow that then observe that every vertex of the graph has even degree because as you drew you had to pass in to that vertex exactly as many times as you passed out.

Using that fact one can show that the result can in fact be 2-colored.

Re the edit: No. For example, a map consisting of several concentric circles is $2$-colorable, but can't be drawn as you're describing.

However, if you add in the condition that your boundaries all connect to each other, the answer becomes "yes", by Euler's famous Königsberg bridge solution.