I'm not a mathematician so I could be completely wrong but aren't square binary orthogonal matrices just permutations of the rows (or columns) of the identity matrix?
If yes,
m = eye(n);
m = m(randperm(n), :)
This certainly generates random binary orthogonal matrices of size nxn. Whether it can generate all the possible ones, I don't know.
