I would like to allow users to chmod a file that is owned by root or some user that is not themselves. I have chmod'ed the file to 777 and I get "operation not permitted". I have added the user to the group of the file and get the same. Why can't a user chmod a file they have write access to?
Unix permissions are designed to be simple. You need the read permission to read from a file, the write permission to write to a file, and the execute permission to execute a file. You need to own a file to modify its metadata¹.
Allowing a user who can read a file to grant others the read permission, or allowing a user who can write a file to grant others the write permission, would not change the security model much. That's because unix permissions are discretionary: a user who can read a file can expose its contents to other users, even if these other users would not otherwise be able to read the file (and similarly for writing, the user could act as a proxy and write on behalf of others).
On the other hand, allowing a user to grant permission that it doesn't have would completely break the permission system: the user could grant all permissions to itself.
It's pretty rare to need to change the permissions of a file that you don't own. Usually you should arrange for the file to have the right permissions as soon as it is created. If you really need that, you might give the user
sudo chmod rights for a particular mode and a particular file (e.g.
joe: ALL = (ALL) chmod g+r /path/to/file).
¹ Except for the access and modification times, which are particular because reading or writing to the file also sets them.
Why can't a user chmod a file they have write access to?
For the normal access rights this is a design decision. You need richacls:
WRITE_ACL and maybe