You can upload an .htaccess file that uses a RewriteRule to make the cgi-bin transparent to your users. Our wiki uses this.
In addition to putting #!/usr/bin/php, you need to make sure your scripts are CHMOD'ed to 750. Good FTP clients can do this.
To prevent anonymous users from sending spam, we don't support sendmail on free accounts, or any outbound mail connections from CGI. Paid users can request sendmail access.
More information on how to set this up can be found at The PHP website.