Yes it is possible to do this via php. Usual linux permissions rules apply however so as you are looking to chmod scripts not owned by the apache user (nobody) and the apache user does not have write permissions then one method is to give apache permission to use sudo
Be warned - this is potentially a massive security hole!!!
You can give apache permission to use sudo by editing the sudoers file. It is recommended that you do not edit this file directly as an error can leave you completely screwed so on my (Ubuntu) system I type
sudo visudo
Then you need to add a line for your "nobody" user. You can restrict sudo permissions to a particular script or folder so i would recommend writing a shell script to change the permissions and then placing this in a folder away from any other scripts. That way apache doesn't have complete root privileges on your system (which is a pretty scary thought). You can also put some code in the shell script to restrict which files can be changed.
You also need to allow apache to sudo without a password as you have no way of entering the password through php. So the line you would add is something like
nobody ALL=(ALL)NOPASSWD:/path/to/my/script
Then in php you just prefix the command with sudo
passthru ("sudo /path/to/my/script ...");
(there are a few other functions you can use instead of passthru(), was just the first that came to mind)
As I said before, this is potentially very dangerous and whilst the above will work, I have only used it on my own private system before, never on a public production server. I'm sure plenty of people will have comments on the security of this so I would be interested to hear what other potential pitfalls and security holes there could be with this method. I know a similar thing can be done using SuExec but am not so familiar with it so if anyone has any pros or cons of SuExec over this method I would be interested to hear them.
Final note: I would change the apache user from nobody to something like 'apache' or 'www' - probably just being silly but I don't like the idea of giving root permissions to a user called nobody!!!
Hope this helps!