1. sudo apt-get purge texlive*
  2. rm -rf /usr/local/texlive/* and rm -rf ~/.texlive*
  3. rm -rf /usr/local/share/texmf
  4. rm -rf /var/lib/texmf
  5. rm -rf /etc/texmf
  6. sudo apt-get remove tex-common --purge
  7. rm -rf ~/.texlive
  8. find -L /usr/local/bin/ -lname /usr/local/texlive/*/bin/* | xargs rm

This finds all the files in /usr/local/bin which point to a location within /usr/local/texlive/*/bin/* and removes them; because we’ve already deleted all of /usr/local/texlive, these are dead links. To see which files are being deleted, replace xargs rm with xargs -t rm (or tee off to a log file, or whatever).