You could use Kerberos to authenticate your CGI script to your runs-as-root script (and vice-versa if you wanted even more security).

To avoid a secret being recorded in your CGI script or one of its configuration files, you could run the script in a persistent environment (e.g. mod_perl) and have an operator enter the secret on startup.

It should be sufficient to authenticate the user once. Securing communications between your CGI script and your runs-as-root script is a separate problem from user authentication.