you can just get an IDE that allows to find and replace ocurrences on all files and then change your date_format function to something else
Most hosts won't just switch to PHP5 and leave PHP4 users in the cold.
It would be corect in the past, but today I don't think so. Zend warned developers to switch to PHP5 due to discontinuing PHP4 over 2 years ago, and fully discontinued it months ago. Any sysadmin knows better than keeping obsolete/discontinued software running on the servers.
The best option available is the "in rome..." solution. even if they somehow support support php4, they'll inevitably remove it later