I've done this with only one frame by having the user
first go to a static html page with javascript in the head.
The javascript checks a cookie and does a redirect to either
a separate static page or to the cgi program.
You can do the same with a perl program by having it output
the static html, or outputting the redirect, but you can't
(as far as I know) set a cookie and do a redirect simultaneously
from Perl.
Also it would be good to provide static links
on the temporary page just in case redirection fails,
i.e. no javascript or cookies accepted in user's browser,
or failure of some useful javascript code due to browser version.
By the way you can also modify the javascript on the fly
if outputted from a Perl program.