The problem with Hamming distance is that it's bounded above by N, so if you have a subset of F_2^N with Hamming distances in that range, you're not going to be able to embed it in F_2^n for n much smaller than N.

Perhaps more natural is to build in a scaling, so that you want to find an embedding f of the subset S of R^N into R^n in such a way that

d(f(x),f(y)) ~ (n/N)d(x,y).

In other words, given two vectors x and y, you want the proportion of coordinates in which they agree to be more or less left alone by the projection. Then you could try a random projection as in Johnson-Lindenstrauss -- i.e. show that (if indeed this is true) a random choice of one of the N choose n coordinate projections gives you low distortion in this sense, when n is not too horrifically small.

The problem with Hamming distance is that it's bounded above by $N$, so if you have a subset of $\mathbb{F}_2^N$ with Hamming distances in that range, you're not going to be able to embed it in $\mathbb{F}_2^n$ for $n$ much smaller than $N$.

Perhaps more natural is to build in a scaling, so that you want to find an embedding $f$ of the subset $S$ of $\mathbb{R}^N$ into $\mathbb{R}^n$ in such a way that

$d(f(x),f(y)) \approx \frac{n}{N}\cdot d(x,y)$.

In other words, given two vectors $x$ and $y$, you want the proportion of coordinates in which they agree to be more or less left alone by the projection. Then you could try a random projection as in Johnson-Lindenstrauss -- i.e. show that (if indeed this is true) a random choice of one of the $N \choose n$ coordinate projections gives you low distortion in this sense, when $n$ is not too horrifically small.