Uma resposta fornecida a essa mesma pergunta nos fóruns do Ubuntu sugeriu o uso do LiveCD para chroot no sistema e reinstalar o Perl. No entanto, usar o chroot para entrar no sistema não evita a dependência do apt e do dpkg no Perl.
Atualmente, a única solução de trabalho que encontrei é a reinstalação do Ubuntu e dos pacotes desejados.