There appears to be support for fine-grained capabilities in Linux kernel, which allows granting privileges to a process to do things like, for example, opening raw sockets or raising thread priority without granting the process root privileges.
However what I'd like to know if there is a way to grant per-user capabilities. That is, allow non-root and non-suid processes to acquire those capabilities.
Yes, you can use setcap to specify a capability set for an executable, which can grant specific capabilities when that executable is run.
From the capabilities(7) man page:
File Capabilities Since kernel 2.6.24, the kernel supports associating capability sets with an executable file using setcap(8). The file capability sets are stored in an extended attribute (see setxattr(2)) named security.capability. Writing to this extended attribute requires the CAP_SETFCAP capability. The file capability sets, in conjunction with the capability sets of the thread, determine the capabilities of a thread after an execve(2).
The way to grant capabilities per-user (or even per-group) would be with a PAM module. sqweek's answer shows how to do this using pam_cap.
I've not confirmed, but I think that this aspect of SELinux may be your answer:
http://www.lurking-grue.org/writingselinuxpolicyHOWTO.html#userpol5.1
