My question now is how can I remove all versions of Perl and start with a completely new version including the necessary additions to @INC?
Well, you don't necessarily need to remove the old versions to build a fresh, self-contained Perl. In any case, you first need to hunt down and eliminate all environment variables related to Perl. In particular, look in your ~/.profile and ~/.bashrc, but environment variables could also be set elsewhere (like some files under /etc, depending on the system). Look for anything Perl-related, including for example source ~/perl5/perlbrew/etc/bashrc. Those would be in particular PERL5LIB, any PATH entries pointing to any specific Perl builds, PERL_MB_OPT, PERL_MM_OPT, PERL5OPT, and really any other environment variables with PERL in the name (see perlrun). If you're unsure about any of these, feel free to ask here.
Then, it depends on whether it's enough to install Perl in your home directory, or whether you want to install it in some system-wide location. For the former, I'd suggest perlbrew. You can clobber ~/perl5/perlbrew/ first if you want to make sure you're getting a fresh start. Of course, if the file permissions on ~/perl5/perlbrew/ allow it, then you can use this Perl on the entire system.
If you wanted to build Perl from source into some global location, like say /opt, then have a look at the INSTALL file. In short, it can be as simple as doing the following in the Perl source directory: sh Configure -de -Dprefix='/opt/perl5.30' && make && make test && sudo make install.
Both of the methods above will set up self-contained Perl builds, that is, their @INC directories will only be located below ~/perl5/perlbrew/perls/perl-*/ or /opt/perl5.30, respectively, instead of being spread out all over the system. You can freely install modules there, and you no longer need to worry about @INC, PERL5LIB, local::lib, and so on. You only need to worry about your PATH pointing to the installation of Perl you want to use, or pointing your shebang line at the correct Perl.
For installing modules, I strongly recommend cpanm, which you can install via curl -L https://cpanmin.us | perl - App::cpanminus (see App::cpanminus). When you're installing modules, you can check which perl and which cpanm to make sure they are from the same installation, otherwise you've got something strange going on with your PATH.
If the installation gets mucked up somehow, you can simply perlbrew uninstall or rm -rf /opt/perl5.30 to clobber them. Keeping a cpanfile with your dependencies is an advantage, since it allows easy re-installation of your modules with "cpanm --installdeps .".
Then, in your crontab file, make sure to call the correct Perl, I recommend doing this with the absolute pathname. So for example, 0 0 * * * /opt/perl5.30/bin/perl /home/user/script.pl arg1 arg2 ....
