You can use binfmt-misc to avoid the need for the #! line, by registering your php5-cgi binary as an interpreter for *.php files. E.g. with Debian binfmt-misc installed:
update-binfmts --install php5 /usr/bin/php5-cgi --extension php
However, you still need chmod +x on the .php file. And Apache will give a rather sad "500 Internal Server Error" if you are missing the +x permissions :( You can improve the error message using mod_rewrite (but not obliviate the need for +x)..