According to the UNIX standard, "The effective user ID of the process must match the owner of the file or the process must have appropriate privileges in order to do this."
The bit about appropriate privileges needs some explanation. On traditional systems, chmod is allowed on all files when the effective UID (on Linux the filesystem UID, but see below) of the process is 0 [i.e. root].
Linux has a system called capabilities, and the CAP_FOWNER bit controls the ability to use chmod on all files. By default, all capabilities are granted when an execve() call creates a root process (either by executing a setuid binary or when the real UID is 0) or when the effective UID is set to 0 (and removed when it is set to a nonzero value), and a set of capabilities including CAP_FOWNER are enabled when the filesystem UID is set to 0 (and disabled when it is set to a nonzero value). Read the manpage for more details.
You mentioned the sticky bit, but omitted the fact that users also may not set the setgid bit on a file when they are not in the group that is assigned to the file. The setuid or setgid bit may also be ignored in additional implementation-defined circumstances.