debsums -ac -r /mnt
Great, thanks! I didn't know about debsums. However, it does not report anything when started from the debian live usb.
4) If, and only if debsums won't report anything unusual - purge vmtoolsd, cleanup anything in /usr/local, change root password, remove any ssh public keys from /root/.ssh/authorized_keys, reboot to normal. 5) If debsums show any file replacements (especially /usr/sbin/sshd, /bin/bash, etc) - reinstall the OS from the scratch.
I will format disk and do the fresh install anyway, but I simply do not understand how something like this could be done. This is the first time I noticed something like this, simply because it is a fresh install.
By the way, do not have sshd installed (and there is no /usr/sbin/sshd). And no suspicious users in /etc/passwd.