Your permissions look ok, and if it was a problem with ExecCGI not being allowed or a bad interpreter you would see a different error message.

I searched a bit and found this info: manpage for httpd_selinux

It sounds like you might need to do this: chcon -R -t httpd_sys_script_exec_t <path to the cgi directory>