Если тег highload поставлен не от балды (вообще-то база на 30 гб - никакая) и в базу действительно идет перманентная нагрузка, от которой избавиться нельзя, то:
1) если есть возможность переключить базу и сервис в read-only - переключаем.
1.1) если нет - пишем в приложении прослойку к mysql-базе, которая сначала делает запрос в новую базу с utf8, потом в старую с cp1251, мерджит результаты.
2) перегоняем построчно/потаблично данные в новую базу, конвертируя на лету. Проверяем, что строка есть в новой базе, удаляем строку из старой базы,
Если же у вас highload поставлен от балды, то дамп, iconv, restore в базу с новым именем. Приложение перед этим потушить, чтобы данные не потерялись (или в read-only базу перевести).