Bei freedom to surf bekommt man eigentlich einen guten Webspace mit cgi-unterstützung geboten. Du kannst dort sogar php4 nutzen.
www.f2s.com
Aber aufpassen: Bei mir hat die Registrierung mit einigen E-Mail-Adressen nicht geklappt. Es kann also sein, dass du einen neuen Account bei einem anderen Provider erstellen musst.
Wenn man PHP3/4, CGI, und/oder sogar noch eine MySQL Datenbank haben will, wird man wohl oder übel ein wenig Geld anlegen müssen!
Die Erfahrung habe ich auch gemacht!
Da gibt es einpaar schau doch mal unter http://www.kostenlos.de/
unter Internet und dann Webspace die haben einpaar Anbieter.
Sind auch zum größten teil ohne Werbung ist aber nur wenig speicher die diese Anbieter vergeben, es ligt so bei 15 - 20 MB.
Ich hoffe ich konnte dir helfen.