Algoritm to sample an even subgraph of a graph
Based on this answer from Math.SE you can construct a simple algorithm for uniformly sampling an even spanning subgraph.
Assume without loss of generality that $G$ is connected (otherwise you can apply the sampling algorithm to each connected component and return the union). Let us denote $G$'s vertices by $v_1,...,v_n$, and given $i&gt;1$ let $P_i$ be some simple path from $v_1$ to $v_i$ (such path exists since $G$ is connected).
Given $A\subseteq\{2,..,n\}$ and some spanning subgraph $H$, define $H^A$ to be the graph obtained from $H$ by flipping the edges in each $P_i$ for $i\in A$, i.e. if $H$ is represented by $x_H\in\mathbb{F}_2^{|E|}$, and $P_2,...,P_n$ are represented by $x_2,...,x_n\in \mathbb{F}_2^{|E|}$, then $H^A=x_H\oplus\left(\bigoplus\limits_{i\in A} x_i\right)$. Note that for $A\neq B$ we have $H^A\neq H^B$. $H^A=H^B$ for some $A\neq B$ iff there exists nonempty $A\subseteq\{2,...,n-1\}$ such that $\bigoplus\limits_{i\in A}x_i=0$ (i.e. the vectors $x_i$ are dependent). Suppose $i\in A$, and let $G_A$ denote the spanning graph represented by $\bigoplus\limits_{j\in A}P_i$. Flipping the edges of any path $P_j$ only changes the parity of the degrees of $v_1$ and $v_j$. Thus, as $G_A$ is obtained by starting with the empty graph and flipping the edges of every $P_j$ with $j\in A$, $deg_{G_A}(v_i)$ is odd, which means $G_A$ is not the empty graph.
Now we can define the following equivalence relation on subgraphs of $G$, $H_1\sim H_2\iff\exists A\subseteq\{2,..,n\}:H_2=H_1^A$. Based on the previous observation, each equivalence class contains $2^{n-1}$ different elements.
The second key observation is that each equivalence class contains a unique even subgraph of $G$. Given a subgraph $H$, for any vertex $v_{i&gt;2}$ with odd $deg_H(v_i)$ flip the edges in $P_i$. This only changes the parity of the degrees of $v_1,v_i$ in $H$. Proceed in this manner until $deg_H(v_2),...,deg_H(v_n)$ are all even. Since the sum of the degrees is always even, $deg_H(v_1)$ must now be even too, which means that the newly obtained equivalent graph $H'$ is an even spanning subgraph. For uniqueness, suppose for the purpose of contradiction that $H\sim H'$ are two different equivalent even spanning subgraphs of $G$, i.e. $H'=H^A$ for some non empty $A\subseteq\{2,..,n\}$. Let $i\in A$ be some path index in $A$, then clearly $deg_{H'}(v_i)$ is odd, since $deg_{H}(v_i)$ is even and its parity is only changed while flipping the edges of $P_i$.
This was covered in the linked answered by Yly. Now you have a simple sampling algorithm that requires $O(|V|+|E|)$ preprocessing time. Execute BFS from $v_1$ to obtain the paths $P_2,...,P_n$. Sample uniformly a spanning subgraph $H$, now for each $v_i$ with odd $deg_H(v_i)$ flip the edges of $P_i$. In this manner you find the unique even spanning subgraph in $[H]$, using $O(n^2)$ time. Uniformity follows from the fact that all equivalence classes have the same size, and each contains a unique even spanning subgraph.