This is summarised at http://www.mediawiki.org/wiki/User:Robchurch/Getting_PHP_5_on_a_cheap_host
Actually, what's more interesting to me is the "Change the default handler" - because that seems to be exactly what I'd asked for in the first place! Merci beaucoup, monsieur Église!
Now I just have to figure out how to install PHP5 alongside PHP4, as well as how to update MySQL without breaking anything - but that should be relatively easy to do, so I should be up and running in no time.
Thanks again for helping me out with this!
-- Frederik