Remember that CGI execution does not need to be restricted only to cgi-bin directories. You can allow CGI script execution in arbitrary parts of your filesystem.
There are many ways to give each user directory a cgi-bin directory such that anything requested as http://example.com/~user/cgi-bin/program will be executed as a CGI script. Two alternatives are:
Place the cgi-bin directory next to the public_html directory:
ScriptAliasMatch ^/~([^/]*)/cgi-bin/(.*) /home/$1/cgi-bin/$2
Place the cgi-bin directory underneath the public_html directory: