Look into one-time password schemes using S/Key. (I think there are Perl modules the handle this, like Crypt::SKey.) It works the following way:

1. You and the user have a share secret passphrase.
2. When the user first logs in, she is asked to provide a challenge password based on N MD5-iterations of the passphrase (S/Key converts the MD5 hex digits into a small group of 3-5 letter words so it's easy for a user to type)
3. Each time the user logs in, the password is based on N-1 iterations. So there's no way a hacker could determine this (well, a crypto guru with that knowledge probably won't care to hack your web site since some three letter agency is paying her big money to do more interesting things ;)
4. When it nears zero, the user resets the passphrase to something different. (Usually initial N is something like 1000)

Information on S/Key can be found at http://lheawww.gsfc.nasa.gov/~srr/skey_info.html.