One solution is to use a separate storage for salts (or hints, really - it doesn't need to be a complex scheme, since we're hashing it anyway).

I do this myself with supergenpass, for when a site's password DB gets compromised (a common enough occurrence these days).

Importantly, this augmented state is a convenience - it's not irreplaceable. If I find myself _without_ my list of hints, I am not completely screwed - I'll just have a harder time logging into those few sites, and it's quite likely I'll remember the right hint after a few tries from memory if I really need to.