Возможно ли сделать следующее средствами MySQL?

Можно, разрешаю. BOOLEAN, BIT или ENUM на выбор.

Думаю лучше смотреть в сторону триггеров

Ну вот в лоб так не выйдет. В оракле или больших БД можно было бы сделать индекс по функции которая для 0 возвращает 0 а для 1 возвращает NULL и тогда обычный unique решает проблему.

Но я бы рекомендовал таки поменять структуру чтобы было «NULL и не-NULL» а не «0 или 1»

Звучит как XY классический. Т.е. явно по ходу некоего процесса были приняты некорректные решения, которые привели к вопросу ТС. Было бы неплохо, если бы ТС озвучил всю хронологию и настоящую задачу.

Причем кол-во записей с 1 может быть несколько (или совсем не быть), а кол-во записей с 0 не более 1 (или совсем не быть).

Можно сделать констрейнт на триггерах before insert/update, в принципе там нужен один селект, посмотреть, есть ли запись с 0. Конечно, если будешь аптейтть это поле в ноль на половине огромной таблице оно встанет раком.