Well, this is just my opinion, but I feel if you remove CGI from core you might as well declare Perl dead (for the web at least). The entry bar to Perl beginners needs to be lower not higher.
As long as CGI is in core, it's a simple step to use it and get on with the business of showing future developers how to do cool stuff on the web. Those helpful tutorials on the web make it easy to 'get Perl' followed by 'use CGI' and end in 'hello world' before anyone loses interest. Without CGI in core, it's 'get Perl' followed by discussion about which CGI modules to use, followed by more discussion about how to get modules from CPAN, ending with the beginner googling the next web tutorial looking for one that 'just works' without all the fuss (and another PHP coder is born). CGI in core is a carrot to get past the Perl learning curve after which, better CGI replacements can be evaluated with more experience.
But it shouldn't be left to rot in core either. Nothing in core should ever be allowed to become stale and outdated. Better that it be updated in CPAN than neglected in core.