While you may work at a hosting company, the client should conform to the server, not the server to the client. Keep the server secure (register_globals disabled, magic_quotes_* off, etc) and then tell the people being hosted it's their responsibility to update their code. Especially since PHP 4 is past EOL.
We upgraded a server that houses a few hundred websites from php4 to php5, and it took maybe 2 hours to work out the kinks of the code for the clients.
You can install php4 and php5 concurrently; however, you'd have to run one as a CGI, and the other as a module. The downside is speed. The CGI will run slower typically.
The version of *nix does not matter, as php5 will run on it. I used to run php4 and php5 together on my windows machine for a while, just to see the differences while I was working on upgrading all my code to php5.
Your best bet is to do what was suggested and if you can, set up a server and move it over to there one at a time. If not, then I'd say you should get your company to let the customers know that they will be upgrading, and to work on fixing their code now as the upgrade will take place in like 2 weeks.