How to create strong passwords in Linux

Boot from a LiveCD, then mount the / harddrive partition. You can now chroot into your harddrive and just run passwd as root there changing the root pw. That's also the way to change to grub password.

Why not authenticate those users for which you only have an unsalted SHA-1 hash of their password by another means than /etc/shadow.

Using PAM, you can have as many authentication modules as you want and stack them as you want. You can keep pam_unix.so for some users and use pam_ldap.so for the rest.