I have not found a real good solution. As I do not want to compile php4 as cgi manually, I cahnged the server to use php4 as mod_php and php5 as cgi.
But if you need php4 and php5 as cgi, I guess you will have to recompile it. If someone finds a solution why the php4-cgi does not work on debian, please let me know. I dont think that debian releases broken php4-cgi binaries, so there must be a minor thing that we missed in the configuration. But I did not find it at google and did not had the time to dig deeper into the problem.