L1 - embeddability of metrics supported on the Hypercube
In general there are all kinds of lower bounds for embedding an arbitrary metric on the hypercube into $\ell_1$. For example, the edit distance cannot be embedded with better than $\log n$ distortion. Note that the Hamming distance itself embeds isometrically in $\ell_1$, so you can't expect to prove any nontrivial lower bound over all metrics on the hypercube.

p.s I don't think the boolean-ness matters at all.