After extensive googling and looking at the man-page, this appears to be impossible.
Qdiscs are controlled by the following type of socket(AF_NETLINK). Qdiscs use netlink sockets to communicate with the kernel. For example, if you opened a socket with socket(RAW), you would set the linux "capability" CAP_NET_RAW to the user you wanted to be able to use raw sockets.
If you read the netlink manpage, you see that they require CAP_NET_ADMIN for other types of operations, but if you use the "setcap" command with this capability and then attempt to manipulate the Qdisc as a that user, it does not appear to work.
If anybody knows a better way (including a patch to the linux kernel), please post.