Not for $n=2$. I'm afraid this answer uses a lot more algebraic geometry than the question; I spent some time trying to remove it and failed.
Suppose, for the sake of contradiction, that $f_1$ and $f_2$ obey a polynomial relation $g(x,y)$. Let $X$ be the curve $g(x,y) = 0$ in $\overline{\mathbb{F}_2}^2$ (the algebraic closure of $\mathbb{F}_2$) and let $\tilde{X}$ be its normalization. So $(f_1, f_2)$ gives a map $\mathbb{A}^2 \to X$ which, since $\mathbb{A}^2$ is normal, must factor through $\tilde{X}$.
This describes $\tilde{X}$ as the image of a rational variety, so $\tilde{X}$ is unirational. For curves, unirational is the same as rational. So $X$ is a genus zero curve (with some number of punctures.) But a genus zero curve defined over $\mathbb{F}_2$ can have at most three $\mathbb{F}_2$-points, so the map $\mathbb{A}^2 \to \tilde{X}$ must identify two of the four $\mathbb{F}_2$-points of $\mathbb{A}^2$. This contradicts that these points are supposed to have distinct images under the composition $\mathbb{A}^2 \to \tilde{X} \to X \subset \mathbb{A}^2$.
I see no reason the result should hold for $n=3$, and have played a little with a counterexample where $\mathbb{A}^3$ maps to a cubic surface, but I haven't found an example yet. For example, $x^2 y + x y^2 + z^2 + z$ is a smooth cubic that passes through all eight points of $(\mathbb{F}_2)^3$ (and even remains a smooth cubic in $\mathbb{P}^2$ through all fifteen points of $\mathbb{P^2}(\mathbb{F}_2)$); I see no reason that we couldn't map $\mathbb{A}^3$ to it.
Observation: The key question is whether there is a polynomial map $\mathbb{A}^n \to \mathbb{A}^N$, for any $N$, which is defined over $\mathbb{F}_2$, has $(n-1)$-dimensional image and is injective on $\mathbb{F}_2^n$. If so, we can easily interpolate $n$ polynomials in $N$ variables so that the composite $\mathbb{A}^n \to \mathbb{A}^N \to \mathbb{A}^n$ is the identity on $\mathbb{F}_2^n$.