I like the Eulerian circuit idea but I find it's almost always easier to use induction when working with trees -- in particular, induction involving removing a leaf and continuing down the tree in that manner. To get that to work in this case requires a bit of modification, but it works. For example, here is a slightly stronger statement:
``A graph $G$ contains a connected spanning subgraph $A$ and a (potentially non-spanning) tree $B$, edge-disjoint from $A$, that contains all of $A$'s odd vertices. Then $G$ contains a spanning connected subgraph of all even degrees."
Proof sketch: Induct on the number of edges in $B$. Choose edge $uv$ where $v$ is a leaf of $B$. If $v$ is odd for $A$, then add the edge $uv$ to $A$ and remove it from $B$. If $v$ is even for $A$, then just remove $uv$ from $B$ without adding it to $A$. Either way, the number of edges in $B$ is smaller, so induction carries you the rest of the way.