How is the PRIVATE KEY actually created in the first place? How is the "Private Key" created in the first place?

I understand that once you have your wallet, you will also gain access to your public key and private key...

But in order to have a wallet address, one first must have a public key and in order to have a public key, one must have a private key.

So back in the days when crypto wallets did NOT exist, how did it happen? 

I am trying to understand what actually happens first. After all, a wallet simply provides a simple view into what is happening on the blockchain (allowing to send and receive), but there is actually no crypto in a wallet, since everything is attached onto the blockchain. 

Actually, what is the data attached too? Is there some sort of account created on the blockchain, that then has private keys, public keys and wallet addresses associated with it?
Speaking of bitcoin (other cryptocurrencies may do things a bit differently but the principles will likely be similar) and simplifying slightly (i.e. not discussing stuff like segwit).

For ECDSA a private key is simply a large (psuedo)-random number. Depending on the particular wallet implementation the private key may be generated and stored, or it may be generated deterministically from a master secret.

The public key is then derived from the private key and the bitcoin address is derived from a hash of the public key.

Bitcoin transactions have "inputs" and "outputs", normally the total value of the outputs must be less than or equal to the total value of the inputs, but there is a special transaction called a "coinbase transaction" that can introduce a limited number of new bitcoins per block and also collect any transaction fees from other transactions in the block. An input of one transaction must satisfy the conditions set in the output from another transaction to spend the value represented by that output.

There are several types of output, but the normal one is/was "pay to pubkey hash". The output contains a hash of a public key (aka a bitcoin address) and the corresponding input must contain the corresponding public key and a digital signature made with the corresponding private key.