Deux paquets .deb (apt:moreutils et apt:parallel) fournissent un fichier /usr/bin/parallel

apt-file search /usr/bin/parallel |grep '/usr/bin/parallel$'

moreutils: /usr/bin/parallel parallel: /usr/bin/parallel

apt-get update && apt-get install moreutils
ls -ld $(dpkg -L moreutils | sed -e '1d') | grep '^-'|awk '{print $9}' | grep -v parallel | cpio -ov --format=ustar |gzip > moreutils.tar.gz
apt-get remove moreutils
cd /
tar xzvf moreutils.tar.gz -C '/'
apt-get install parallel

C'est pour l'exemple avec cpio. Mais c'est pas très propre. Il contraindrait d'utiliser dpkg-divert