It is not nescessary that a cgi-bin is inside the web directory, as the directory is configured via a script alias. For security reasons, cgi directories should not be inside the web directory. You can access the cgi files with http://www.yoursite.com/cgi-bin/
... as usual.
A second question I have is why do users get their own "web" directories? Are they able to have their own sites and if so how does this work exactly? Do they essentially get their own "Site" (aka "Web") or is this somehow a sub-site (sub-directory, sub-domain) of the defined Site?
This is the user website feature, it is described in the manual. It works with the apache rewrite functions.