This is just a partial answer:
Let $A$ be a $N \times N$ Toeplitz matrix, and consider the sequence of matrices $A_n$ for $n>N$ where we increase the size of $A$ to $n\times n$ and the new diagonals are filled with 0. Then the sequence of determinants $|A_n|$ will satisfy a linear recurrence.
The zeros in a linear recurrence appears either in arithmetic progressions,
or are sporadic. There is an upper bound on the number of sporadic zeros in linear recurrences, and these are "quite rare" in some sense.
To have an infinite number of zeros in this sequence of determinants, we require that the symbol of the matrix have roots of unity, (this is sort of the same as the characteristic equation for the linear recurrence). Now, since the matrix is binary,
the coefficients of the symbol (a polynomial) are also either 0 or 1.
So, in some sense, the question is related to the probability that a polynomial with coefficients either 0 or 1 has a root of unity.