1. Заменить в коде все mb_ функции на их немногобайтовые аналоги. Возможно, это породит определенные глюки, а может и пронесет.
2. Написать собственные аналоги этих функций. Мартышкин труд, но это будет работать.
3. Попросить админов установить на хостинг расширение mb_string, тем более, что сейчас его наличие де-факто является стандартом.
4. Сменить хостинг.
Я обычно начинаю с третьего пункта
