Why on earth would your host require that?
Anyway, there is a php solution you can employ. Just loop through the directories([man]opendir[/man] and [man]readdir[/man] (look in user comments for a recursive solution)) in question and [man]file_get_contents[/man] for each file, then [man]fopen[/man] in write mode(w+ would be good here to truncate the file), [man]fwrite[/man] your shebang line, fwrite the contents of the file, then [man]fclose[/man] the file.
Probably sounds more complicated than it really is, but it should be a fairly small script.