Comprehensive information about hash salts
If a hacker has access to your database system, you're fsckd. Your system has to have access to both tables to run, so the likelihood of "hiding" one from a hacker who's already compromised the system is nearly zero. Not remotely worth the extra complexity, in my opinion.
Having a "nonce" added (in addition) to a salt for each password is not a great help, but doesn't really hurt anything either.
Even 16 bits of salt is typically enough to make password cracking infeasible, if done correctly. I would probably use 64 or 128 bits, why not?
You should use a "good" source of randomness, but it doesn't need to be perfect. If the random values are somehow visible to an attacker, then they may be able to find a way to predict the next random value, but they would have to do this when the password is created and it would only get them that one password.
In short, you need per-user salt and a good hashing function. MD5 is terrible, and SHA-1 is no longer "good". You should be using a system like bcrypt to force an attacker to spend a considerable fraction of a second on each hash. 0.1s per password check is probably no big deal to you, but it's devastating to any kind of brute-force cracking.
This is required reading for anyone implementing a password security scheme:
Regarding #1, you can probably assume that if the users table is compromised, they probably will also compromise the salt table, even if you protected it better somehow. It would only slow them down a bit, like a speed bump would do.
Regarding #2, a hard coded salt value is often easily reverse-engineer-able via decompilation or runtime memory inspection, even with moderate amounts of code obfuscation. This would only help increase security in the case where your application is strictly hosted and nobody is able to get hold of your compiled application.
Regarding #3: What is the optimal length for a password hash? (SO link) - 16 is good!
Regarding #4, it isn't much more work to implement "more truly" random numbers, depending on the platform you're working with. For example, if you can tradeoff some performance to generate your seed/random number, you can probably breathe easier over how truly random your salt is.
No. Using salts correctly will multiply the time it takes for an attacker to crack all the passwords in your database by a factor of millions. Putting salts in another table will add 30 seconds to the time it takes for an attacker to get the salts too.
Yes. It is not a bad idea to use both a global key and a per-user salt.
A salt is, or should be, a cryptographic key. Make it long and random. Database size is not an issue. The salt, like any cryptographic key, can be 128 bits or 16 bytes (32 bytes when stored in hex format).
Your computer should have cryptographically strong pseudo-RNG. Check the security or crypto APIs for your language.