Ясно. Корректно перекодировать такие крякозябы можно только с доступом к консоли сервера. Необходимо создать дамп такой командой.
mysqldump --user=root --password=pass --default-character-set=cp1251 db_name > dump.sql
root - Это пользователь MySQL, pass - его пароль.
Ключ --default-character-set=cp1251 позволяет сохранить верную кодировку.
db_name - Имя базы данных.
Если в базе данных таблицы с разными кодировками, то сохранять их надо отдельно, для чего необходимо их перечислить после имени базы данных.
После создания дампа потребуется его открыть в текстовом редакторе (рекомендую Notepad++) и отредактировать в структурах таблиц кодировку поменяв ее с cp1251 на utf8 (в сравнениях полей тоже).
Отредактированный дамп можно импортировать в phpMyAdmin выбрав кодировку файла windows-1251.
Если на хостинге нет доступа к консоли, то потребуется перенести данные на локальный сервер (домашний компьютер) и уже на нем провести все вышеперечисленные работы. Но в этом случае велика вероятность, что данные будут восстановлены не полностью, как правило получаются битые символы, вроде искаженных букв И и Ш.