Despite your claim of not having any means to store a salt, you do (possibly without realizing): You obviously are storing the username and the hash of each user's password. The same storage could be used to store one more item for each user, a random per-user salt.
You also do not need any additional information about the user to generate a salt. You only need a random number generator once, when the user account is created. Hence you only need a good source of entropy, which of course is more easily said than done on a headless server.
Maybe the confusion stems from the fact that the term "salt" is sometimes used in different meanings. Some authors seem to use the term "salt" for a global (constant) additional input used to calculate the password hashes. Whilst good enough to foil some rainbow attacks, that is not a very good way to implement a salt. A better way is to choose a different salt for each user. Many implementations, e.g. PHP's crypt function, even append the salt (and some hashing parameters) to the computed hash value for convenience, relieving you of having to separately store and retrieve the salt.
A few programmers dislike storing the salt in a database, arguing that the salt could protect in the scenario that an attacker obtains the password database but not some global salt possible hard-wired into the authentication code. I suspect you might be of this persuasion based on your comment about not having a remote database. Please consider that such an argument can be dangerous: If you build on the assumption that your password database may be compromised but some external source of information (the salt or salts) is not, then you are much better off securing your per-user password database as well as this additional store of per-user information. They fulfill the exact same function and hence should be equally easy (or hard!) to secure.