Will all the key pairs that ssh-keygengenerates be unique (not taking collision into account at this point)?
Yes, every key pair will be unique, with well above 99.99999% probability. This is largely due to the size of the key space and the quality of the CSPRNG that is used (see below).
If yes, how does ssh-keygen assure that all key pairs that different people generate at different times are unique and do not end up being the same?
It makes no such assurances, but it is effectively guaranteed to be unique anyways. This is because the OS uses a high quality CSPRNG (Cryptographically Secure Pseudo-Random Number Generator) algorithm that is much more reliable (meaning, more unpredictable) than the out-of-the-box PRNG you get with most languages.
If no, on what factors does the uniqueness of a key pair depend? Other than key length space, and PRNG.
The uniqueness comes from the CSPRNG, not a "regular" PRNG. The difference is the choice of entropy.
A PRNG simply takes some seed (usually either "0" if a programmer is lazy, or some arbitrary measure, such as from time()), shuffles the bits around every time something asks for bits, then does more shuffling. It only "appears" to be random until you observe the output for some period of time, at which point you can determine (a) which seed was used, and (b) the next infinite number of outputs that will be observed from that particular PRNG.
A CSPRNG, by contrast, builds entropy the longer it runs. It does this by taking periodic readings from multiple devices and applying some pretty complicated abstractions to the incoming data to generate a pool of "random" bits. This means that if you're running a flavor of Linux when you loaded this answer, odds are some bits of this answer are now floating in your entropy pool (until they are used, at any rate).
Logically, of course, these bits are random in the sense that computers do not actually have the capability to do "random" things (they always precisely follow the instructions given to them), but they are nevertheless random in the sense that no generic algorithm devised by either man or machine can possibly hope to determine the original entropy numbers, which is being constantly replenished as random numbers are generated.
Since computers often receive different types of input from the network, disks, and so on in fairly unpredictable order (because of latency, retries, other physical characteristics of hardware), it would be impossible for two systems to be perfectly synchronized to the point where the CSPRNG would also be in sync. Similarly, it'd be impossible to predict the output of a CSPRNG unless you were literally debugging the kernel, and the very act of doing so, or trying to report the current state, would alter the state of the CSPRNG.
Of course, the official documentation is quite clear on this: it's all theoretical, as we have no way of proving that no key will ever be generated twice. However, the odds are so incredibly stacked against ever finding a random key that was a duplicate that one may as well say it is indeed impossible.