EDIT :
I've edited the argument to make it stronger
Suppose that $m\geq 3$ and $n\geq 5$ so that there is a 3x5 submatrix A. I show that the number of possibilities is zero in this case.

In A, there are at least two rows with at least there $1$'s each (up to relabeling the symbols). Since we cannot have a constant 2x2 submatrix, we may assume that the first two rows of the matrix are 
[11100] and
[00111].

To avoid a 2x2 contant submatrix, the first two entries of the third row must be different, but then, whatever choice we make for the third one, we will get a constant 2x2-submatrix in the first and third row.


The answer for $m=1$ and $m=2$ is not hard to calculate explicitly.

Together with the answer above, this reduces the problem to checking the following cases (which is not too hard):
3x3,3x4,4x4.