I wouldn't recommend trying to remove the base Ubuntu Perl. It is used extensively by the system and many other software packages that are part of the base installation.

Unfortunately, I don't think current Ubuntu has a package for Date::Format (it would be called libdate-format-perl)

My recommendation would be to use CPAN (or http://cpanmin.us), and possibly install your own Perl via Perlbrew. This last step is not strictly necessary, but the Ubuntu base Perl tends to lag behind a few versions. Perlbrew is careful not to interfere with the base Perl on the system.