What does high variance mean in a binary classification machine learning model?
You have correctly intuited that variance isn't as useful a concept in this case. Statisticians typically look at the binomial deviance instead (see here for a thorough technical development).

If you do want to think about variance, we can recognize that many binary classifiers output an estimate of the label $\hat{Y}$. It helps here to think of a randomized classifier which estimates $P(Y=1|X=x) = E[Y|X=x]$ (call this estimate $\hat{p}(x)$) and generates $\hat{Y} = 1$ with probability $\hat{p}(x)$, $\hat{Y} = 0$ otherwise. We have $$var(\hat{Y}|X=x) = E[(\hat{Y} - E[\hat{Y}|X=x])^2|X=x].$$ This will be smaller when the classifier is more certain about the classification once it sees the covariates. I.e., if $\hat{p}$ is always either 1 or 0, then the variance is 0 (but of course the bias will be huge). If there are equal numbers of each class in the training data and the classifier is able to learn nothing from the covariates, then $\hat{p} = \frac{1}{2}$ for any $x$ and so the variance is $\frac{1}{4}$--a coin flip, as we'd expect.