First, if PHP is running in safe mode, shell_exec() cannot be used.
PHP scripts run with the same permissions as Apache, those of the "www-data" user. That means the www-data user must be able to see and execute the file. If you have root privileges, put the script in /var/www for testing purposes with user and group www-data and execute privileges. Can you run it from there? Can you run any script from there, even a simple one like
echo "$(date +%c) - I was called" >> /var/www/test-script.log