The answer is yes.
The proof is as follows: If there is a Hamiltonian cycle $f: \{0,...,2^{2^n}-1\} \rightarrow \{0,1\}^{2^n}$ of the hypercube where the number of edges of a given direction in the Hamiltonian cycle are the same, then there is such a bijection $\varphi$, by setting $\varphi_m(x)=\sum_{k=1}^m f_k(x)$, $m=1,2, ... 2^n$ (i.e. taking the cumulative sum of $f(x)$). Such a Hamiltonian cycle will be called a balanced Hamiltonian cycle.
My construction of balanced Hamiltonian cycles is inspired by this paper, which provides balanced Hamiltonian cycles for $n=1,2,3$. The construction for $n=2$ will serve as the base case of mathematical induction.
Assume the existence of a balanced Hamiltonian cycle for $n$, and make it a directed cycle. Let $g$ be a function on $\{0,1\}^{2^n}$ where $g(x)$ is the next vertex of $x$.
Let $h(x)$ be an involution on $\{0,1\}^{2^n}$ such that there are exactly $2^{2^n}/2^n$ values where $x$ and $h(x)$ differs at the $k$th bit, $k \in \{1 ... 2^n \}$. (The existence of $h$ will be proven later.)
Then there is a balanced Hamiltonian cycle on the hypercube of dimension $2^{n+1}$.
Let's identify the $2^{n+1}$-dimensional hypercube by the Cartesian product of the $2^n$-dimensional hypercube with itself. Let $(a_0, b_0)$ be a vertex of the $2^{n+1}$-dimensional hypercube. The sequence $(a_k, b_k)$ is defined as follows: if $k$ is odd, then $(a_{k+1}, b_{k+1})=(a_k, g(b_k))$; if $k=0 \text{ or } 2
(\text{mod } 2^{2^n+1})$, then $(a_{k+1}, b_{k+1})=(g(a_k), b_k)$; otherwise $(a_{k+1}, b_{k+1})=(h(a_k), b_k)$
One can see the function $k\rightarrow (a_k, b_k)$ plays the role of $f$ for $n+1$. The point is to analyze a cycle of length $2^{2^n+1}$, conclude that $(a_{2^{2^n+1}m}, b_{2^{2^n+1}m})=(g(g(a_{2^{2^n+1}(m-1)})),b_{2^{2^n+1}(m-1)})$ and it follows that $(a_k, b_k)$ traces out a Hamiltonian cycle (i.e. you need $m=2^{2^n-1}$ for the point to return to $(a_0,b_0)$). It's easy to check the Hamiltonian cycle is balanced.
Now we only to prove the existence of $h$.
If $n=2$, then such $h$ exists:
0000 - 0001
1110 - 1111
0010 - 0110
0011 - 0111
0100 - 1100
0101 - 1101
1000 - 1010
1001 - 1101
Assume the existence of $h$ for $n$. Choose a subset $K$ of $\{0,1\}^{2^n}$ with size $2^{2^n-1}$ that is closed under $h$ and there are exactly $2^{2^n-1}/2^n$ elements $x$ in $K$ where $x$ and $h(x)$ differs at the $k$th bit ($k \in \{1 ... 2^n \}$).
Define a function $p$ on $\{0,1\}^{2^n} \times \{0,1\}^{2^n}$: $p(a,b)=(a,h(b))$ if $b \in K$, otherwise $p(a,b)=(h(a),b)$. Then $p$ plays the role of $h$ for $n+1$.
$\newcommand{\R}{\mathbb R}\renewcommand{\le}{\leqslant}\renewcommand{\ge}{\geqslant}$Let $n:=m\ge2$.
We will show that the desired condition holds if and only if
$$p\ge\frac{\lceil n/2\rceil-1}{2 \lceil n/2\rceil-1}.$$
Suppose for a moment that there exist random variables $X_1,\dots,X_n$ such that $X_i\sim {\rm Ber}(1/2)$ for all $i$ and $P(X_i=X_j)=p\in(0,1)$ if $i\ne j$. That is, there is a nonnegative function $g\colon\{0,1\}^n\to\R$ such that
(i) $\sum_{x\in\{0,1\}^n}g(x)=1$,
(ii) $\sum_{x\in\{0,1\}^n}1(x_i=0)g(x)=\frac12$ for all $i$,
(iii) $\sum_{x\in\{0,1\}^n}1(x_i=x_j)g(x)=p$ if $i\ne j$.
Then, by symmetry, conditions (i)--(iii) will hold with $\tilde g(x):=\frac1{n!}\sum_{\pi\in S_n}g(\pi(x))$ in place of $g(x)$, where $S_n$ is the set of all permutations of the set $[n]:=\{1,\dots,n\}$. Note that $\tilde g(x)=f(\sum_1^n x_i)$ for some function $f\colon\{0,\dots,n\}\to\R$ and all $x=(x_1,\dots,x_n)\in\{0,1\}^n$. Moreover, the conditions (i)--(iii) can be rewritten as
(I) $\sum_{k=0}^n \binom nk f(k)=1$,
(II) $\sum_{k=0}^n \binom{n-1}k f(k)=\frac12$ for all $i$,
(III) $\sum_{k=0}^n a_{n,k} f(k)=p$,
where
\begin{equation}
a_{n,k}=\binom{n-2}k+\binom{n-2}{k-2};
\end{equation}
of course, $\binom{n-2}k=0$ if $k\ge n-1$ and $\binom{n-2}{k-2}=0$ if $k\le1$.
Thus, for any given $n\ge2$ and $p\in(0,1)$, we want to see whether there is a nonnegative function $f\colon\{0,\dots,n\}\to\R$ such that conditions (I)--(III) hold.
Consider the ratios
\begin{equation}
r_k:= r_{n,k}:=\frac{a_{n,k}}{\binom nk}
=\frac{(n-k)(n-k-1)+k (k-1)}{n (n-1)}.
\end{equation}
Note that $r_{k+1}\le r_k$ if $0\le k\le\frac{n-1}2$ and $r_{k+1}\ge r_k$ if $\frac{n-1}2\le k\le n-1$. Also, $r_k=r_{n-k}$.
It follows that
the maximum, say $\overline p_n$, of $\sum_{k=0}^n a_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that condition (I) holds is attained if $f(0)=f(n)=\frac12$ and $f_1=\cdots=f_{n-1}=0$, and hence $\overline p_n=1$; moreover, then condition (II) happens to hold as well;
if $n=2m$ is even, then the minimum, say $\underline p_n$, of $\sum_{k=0}^n a_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that condition (I) holds is attained if $f(m)=1/\binom nm=1/\binom{2m}m$ and $f_k=0$ for $k\in\{0,\dots,n\}\setminus\{m\}$, and hence $\underline p_n=\underline p_{2m}=\frac{m-1}{2m-1}$; moreover, then condition (II) happens to hold as well;
if $n=2m+1$ is odd, then the minimum $\underline p_n$ of $\sum_{k=0}^n a_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that condition (I) holds is attained if $f(m)=f(m+1)=\frac12/\binom{2m+1}m=\frac12/\binom{2m+1}{m+1}$ and $f_k=0$ for $k\in\{0,\dots,n\}\setminus\{m,m+1\}$, and hence $\underline p_n=\underline p_{2m+1}=\frac m{2m+1}$; moreover, then condition (II) happens to hold as well.
So,
the maximum of $\sum_{k=0}^n a_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that conditions (I) and (II) hold is $\overline p_n=1$;
if $n=2m$ is even, then the minimum of $\sum_{k=0}^n a_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that conditions (I) and (II) hold is $\underline p_n=\frac{m-1}{2m-1}$;
if $n=2m+1$ is odd, then the minimum of $\sum_{k=0}^n a_{n,k} f(k)$ over all nonnegative functions $f\colon\{0,\dots,n\}\to\R$ such that conditions (I) and (II) hold is $\underline p_n=\frac m{2m+1}$.
The set of all values of $\sum_{k=0}^n a_{n,k} f(k)$, where $f\colon\{0,\dots,n\}\to\R$ is a nonnegative function such that conditions (I) and (II) hold, is convex and therefore coincides with the interval $[\underline p_n,\overline p_n]=[\underline p_n,1]$.
Thus, the following two conditions are equivalent to each other:
there is a nonnegative function $f\colon\{0,\dots,n\}\to\R$ such that conditions (I)--(III) hold;
$\underline p_n\le p\le1$.
That is, for each natural $n\ge2$ and each $p\in[0,1]$, the following two conditions are equivalent to each other:
One may also note that
$\underline p_n=\dfrac{m_n-1}{2m_n-1}$, where $m_n:=\lceil n/2\rceil$;
$\underline p_n\le\underline p_{n+1}<\frac12$ for all $n\ge2$;
$\underline p_n\to\frac12$ as $n\to\infty$.
Best Answer
$\beta$ cannot be too much larger than $1/2$; namely we must have $\beta \leq k/(2k-2)$.
To prove this, identify the $x_i$ with vectors $v_i \in {\bf R}^n$ each of whose coordinates is $1$ or $-1$, and consider these vectors' dot products. Clearly $v_i \cdot v_i = n$, and more generally $v_i \cdot v_j = n - 2 d(x_i,x_j)$, which for $i \neq j$ implies $v_i \cdot v_j \leq (1-2\beta') n$ where $\beta' = \beta - \gamma$ is arbitrarily close to $\beta$. On the other hand $s := \sum_{i=1}^k v_i$ must satisfy $s \cdot s \geq 0$. Thus $$ 0 \leq s \cdot s = k n + \sum_{i\neq j v_i \cdot v_j} \leq kn + (k^2-k) (1-2\beta') n = kn\left(1 + (k-1)(1-2\beta')\right), $$ whence $2\beta' - 1 \leq 1/(k-1)$. Therefore $\beta \leq k/(2k-2)$ as claimed.