Normally you'd =not= store the salt separately; the usual way is keeping the salt and the password together in the same 'blob'

Rehashing can be safely implemented as long as the auth. process can handle both md5 and some composite hash [i.e. shash(md5(pwd))]

It's really a trivial operation.