Find hamming codewords in r=2^k dimensions
I completely misunderstood Misha's answer. Here is my updated understanding of the equivalent problem. All quotes are from his answer.


Let $S = \{0,1\}^{r-1}$, $|S| = 2^{r-1}$ bit arrays, each bit array has length $r-1$.
Let $S_i = \{x\ |\ x \in S\ and\ x_i = 1\}$, where $x_i$ is the $i^{th}$ bit of bit array $x$. We set the $i^{th}$ bit of array $x$ to $1$.

An even number of bit arrays is always chosen from $S_i$. If initially an odd number of bit arrays is chosen, then choose the bit array corresponding to the parity bit as well, so finally an even number of bit arrays are chosen.

This corroborates with Misha's answer, as the coordinates numbered off exactly match the parity bit coverage.


  
  Among the coordinates numbered $0\dots001, 0\dots011, 0\dots101, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
  Among the coordinates numbered $0\dots010, 0\dots011, 0\dots110, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
  

Repeat step 2 for all $i \in [1,\ r-1]$.

Let $A$ be the set of chosen bit arrays from $S_i$ for all $i$, where chosen bit arrays are hamming codewords.

The hamming code is an even parity bit, single error correction code for arrays of length $r - 1$.

The following describes single error correction, where "vertex" means "bit arrays", and "picked vertices" means "bit array in $A$" or "hamming codeword".


  If a vertex is not one of the picked vertices, find all the parity conditions that fail, let $i$ be the coordinate with a $1$ in all the bits corresponding to the failed conditions; change the $i^{\text{th}}$ coordinate, and you will get a picked vertex.



This solves the equivalent problem of finding set $A$.



Now, to solve the original problem.

(I originally thought the $00\dots00^{\text{th}}$ coordinate was for double error detection, and was wondering why I needed that in a single error correction code. I was completely wrong.)


  Given a vertex, if it is one of the picked vertices, change the $00\dots00^{\text{th}}$ coordinate, and you will get another picked vertex.


This is equivalent to prepending a new bit, $b$, for each bit array within the set $A$ that we derived earlier, thus making all bit arrays have length $r$.

Arbitrarily let bit $b = 0$. Define $A_{new} = \{b\ x_1\dots x_{r-1}\ |\ x \in A\}$.

Let $B = \{\neg b\ x_1\dots x_{r-1}\ |\ x \in A\}$, so all bit arrays are same as $A_{new}$, except for every array, the $b$ bit is flipped.

This fits well with Misha's explanation that bit arrays from $A_{new}$ and $B$ are nearly-identical, because the only difference is the flipped bit $b$.


  the $00\dots00^{\text{th}}$ coordinate of a vertex [...] is the "free" coordinate where we pick a vertex with $0$ and also pick a nearly-identical vertex with $1$.


This solves the original problem, such that the $2^r/r$ bit arrays are in sets $A_{new}$ and $B$.