Also ich hab das (in Virtualbox) auf einem ziemlich frischen 12.04 getestet, das deb nicht gesehen (ist aber noch da), sondern das tar.gz. In der darin enthaltenen Anleitung wird der Installbefehl so, wie ins Wiki eingetragen, angegeben. Ausserdem kann _ohne Installation_ direkt gestartet werden. mercurial hab ich nicht benötigt, die Explizitangabe auch nicht. Python3 war installiert, vielleicht liegt es daran.
Ergänzung: Readme: "Installation
Installation should be as simple as "./setup.py install" on Unix based systems.... Those with debian based distros will probably be
insterest in --install-layout=deb.
Installation is not necessary, since djvubind can run straight from the unpacked source.
N.b., at the moment most distributions are able to have python3 installed but do
not use that version by default. If this is the case
explicitly call python3 when installing (e.g. "python3 ./setup.py install")