Hmm... i don't know if these hosts have cgi support, but they have php support for sure:
Try www.xug.net & www.php50.com ..