Auto adding cronjobs is likely a bad idea. Speaking UN*X terms here,some systems have an /etc/cron.d/cron.allow which needs the username added before the user is allowed to add a cronjob. I really think you are going to need to assume that someone installing your script is a sysadmin or rethink your distribution strategy.

You can make the admin's job easier by providing the pregenerated crontab information like producing a file that can be read-in like
% cronatab -e < crontoload.in

But know that admins may want to put scripts in certain places so you probably can't assume that your crontab will work perfectly every time depening on where perl is installed, the module dependancies, etc. I think that you are going to have to assume some sort of computer competency if someone is running linux and needs to run your script to optimize your CGI script's performance.

As for pure-perl solutions, you could consider Schedule::Cron but I'm not sure how safe it is having never used it. It would run as userlevel daemon and if your webserver is running as nobody you won't be able to cleanup files produced by it.