Имеется некая таблица MySQL в которой есть  некие  записи,  пусть  это
будет таблица "контакты". Имеется ряд операторов, которые  работают  с
этой таблицей, им постоянно автоматически выбирается свободный контакт
из таблицы "контакты".

Необходимо реализовать скрипт  работы  операторов,  чтобы  им
постоянно выдавался контакт, который свободен на данный момент. Причем
не должна произойти ситуация захвата одного контакта двумя операторами
за один сеанс работы.

Решается ли эта задачка с использованием транзакций MySQL или нужно копать в другом направлении?

Можно транзакциями, можно блокировкой таблиц.

Либо не так чтобы очень правильно, но иногда проще - сделать у контактов поле `operator` где хранится оператор, который работает с контактом или NULL если он свободен.

Потом как-то так:

При использовании транзакций, во время её выполнения таблица будет заблокирована и не доступна для других пользователей, запросы будут вставать в очередь и ждать пока отработает транзакция.
при 10 запросах в секунду это не критично. но для серьёзной базы, я бы искал другой способ...
Ну и приведённый выше пример тоже не так плох.