Thinking of your vectors as (column) bitvectors, here is a concrete description of how you can proceed, using (non-reduced) column-echelon form for a basis of $\langle e_1,\ldots,e_n\rangle$. Separate your vectors $e_i$ into a "basis" (initally empty) and a "rest" (initially everything). For each bit position in order, search a vector in the rest where this bit is set (1). If one is found, move that vector into the basis, and clear any bits that are set in that position in the rest, and in $v$, by adding (XOR) that basis vector. If no vector in the rest is found, but the bit in that position in $v$ is set, then this proves $v\notin\langle e_1,\ldots,e_n\rangle$; conclude that and stop. If you reach the final bit position without this happening then $v$ has been reduced to $0$ which proves $v\in\langle e_1,\ldots,e_n\rangle$.
If you have just one vector $v$, then you can replace the basis by the bitbucket, as its vectors are clearly never used once they have settled there. If you have more vectors to test though, keeping a list of basis vectors and their initial set bit positions may speed up the test for successive $v$s. I'll let you estimate the complexity of this procedure yourself; I don't think there is much hope of doing better.