What's your distribution? Do you have a specific script that absolutely requires PHP4, or are you just trying to see if it's possible?
Howtoforge used to have some tutorials for installing both PHP4 and PHP5 using (Fast)CGI, but that was several years ago.
Most distros don't even ship PHP4 these days, because PHP4 hasn't received security update in over two years. You may have to hunt down the 4.4.9 source code and compile it yourself.
The web hosts that still support PHP4 do so at their own risk. Actually, if I were choosing a web host, I'd avoid the ones that even mentioned PHP4 because it's a time bomb just waiting to blow up.