How to fix insecure password storage security in a database

Jeremy Collake has a great post that describes a simple, elegant solution for migrating a weakly-encrypted password field in a database. LinkedIn's password database was leaked recently, and it turns out that all they did to secure user passwords was run them through a very well-known algorithm called SHA-1, which doesn't take much to brute force and recover passwords. They did this without adding any "salt" or uniqueness to the algorithm, making it trivial to brute force using a rainbow table.

To add a more secure algorithm without requiring the users to login, simply "hash the hash." Quoting from the article:

So, if the original algorithm was:
SHA1(password)
The new algorithm would be, hashing the hash:
SHA2-512(SHA1(password))

On user login, of course, you simply run the password through SHA2-512(SHA1(password)).

What's significant in the LinkedIn password leaks, is that they didn't add anything to the SHA-1 algorithm when hashing passwords. Ideally, you should apply what's called a "salt" to a hashing algorithm which makes it harder to crack. Taking an example from the article:

SALT^SHA2-512(SALT^SHA1(password))

Obviously, the above examples are simplified, and actual implementation would be different depending on your specific scenario.

This is one way to solve the insecure password database problem. How would you fix it?