As I have figured out recently, the answer is no. The full proof is somewhat technical and I cannot supply full details within the framework of an MO post, but here is the idea of behind the construction.
Start with a symmetric matrix $A\in{\mathcal M}_{n\times n}(\{0,1\})$ such that the Perron-Frobenius eigenvalue of $A$ is much larger than the absolute value of any other eigenvalue, and the corresponding eigenvector is "reasonably simple". Now take a high tensor power of $A$. We get a symmetric zero-one matrix $M$ which inherits the spectral gap of the original matrix $A$, and hence the norm $\|Mx\|$ is controlled by the projection of $x$ onto the Perron-Frobenius eigenvector, say $v$, of $M$. Being a tensor power of the Perron-Frobenius eigenvector of the original matrix $A$, the vector $v$ can be analyzed, and with some effort can be shown to be "oblique" in the sense that it is "not aligned" with any zero-one vector. Hence, if $x$ is a zero-one vector, then the projection of $x$ onto $v$, and therefore the norm $\|Mx\|$, are small.
A precise result I was able to prove along these lines is as follows: there exist matrices $M\in{\mathcal M}_{n\times n}(\{0,1\})$ of arbitrarily large order $n$ such that for any non-zero vector $x\in\{0,1\}^n$, we have
$$ \|Mx\| \ll \left( \frac{\log\log n}{\log n} \right)^{1/8} \|M\|\|x\|. $$
