Почти всеми, а вообще если надо что-то специфическое то берите впс и туда ставте то что вам нравиться.

Найти нормальный хостинг с MySql 4 почти не возможно!.
А зачем Вам MySql? Это довольно старая версия, найти ее шансов очень мало, т.к. некоторые популярные движки перестали поддерживать MySQL 4.
Например
- WordPress 3.2 будет работать MySQL 5.0.15 и выше.
- Joomla 1.7.x будет работать MySQL 5.0.4 и выше.
Вывод на MySql 4 поставить новую Joomla и WordPress не получится. И именно по этому все адекватные хостеры давно обновили у себя MySql как минимум до 5.0.15.

Единственный вариант брать VPS, но стоит ли игра свеч?

Вряд ли .... проще впс за 1 доллар найти и установить самому.