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.
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