But my question is still standing: are the bitcoin addresses created as new or have they all been created and given to each new user at random?
There is no massive database (or something like that) which holds all possible private keys and a new address is taken from there. Instead an address is generated at random, something which you could/should do locally.
In short and a bit simplified:
Truly Random Input -> SHA-256 ->
Private KeyPrivate Key -> ECDSA ->
Public KeyPublic Key ->Add some checks -> Encode with Base58 ->
Bitcoin AddressIf the input is truly random there is no way two of the same Private Keys will be generated. So go ahead, you can literally generate million of keys/addresses yourself to use without even a slight risk of finding one which has been found/used before.