What gets output when you run /usr/bin/php -v on your server? The error message you quoted is what you get when there’s something at /usr/bin/php but the output doesn’t look like what we’re expecting.
Here’s something to consider: maybe PHP’s exec function is disabled? Some shared hosts like to do that to try to stop their users from executing other programs. The PHP setting is disable_functions or you can check with your host if you have one.