1) How to generate a private key safely?
With your explanation, I think you are guru enough to generate private key safely. There are different methods of doings this, you can decide to use a paper wallet website offline, like bitaddress.org in case you want to hold, you can decide to download electrum on airgapped device to generate it, you can decide to use a multisig wallet, you can decide to buy hardware wallets like trezor which is completely open source and private key generation on it is offline.
2) I do not want to use any 3rd party software as a wallet.
Like electrum, it is open source, there are ays you can even run it offline, trezor is also offline wallet. If a wallet is en source and it's sormurce cold is available to the public, I think this is sufficient enough to trust the wallet.
Suppose I just store my private key on a piece of paper and later transfer coins into it using exchanges. Would that be a valid transaction and allows me later to spend these coins?
Yes, it will be a valid transaction, but making sure you track the transaction on blockchain to be certain that the transaction is valid and confirmed.
Is there anything else I need to store together with the private key (like the hashed transaction number in transaction_input in the blockchain?
It depends, if it is seed phrase you generated using wallet, the seed phrase is enough. If it is extended with passphrase, you will need to make a backup of the passphrase. If it is private key that was generated, and you encrypted it with BIP38 passphrase, you will need to backup the password used for the encryption.
(Say if I use some sophisticated cold wallet, I may experience hardware degradation in 10 yrs, no one at that time used this software, programmers 10 yrs ago cannot be reached, and any trick in coding or encoding in the original version becomes obsolete. I would be a consumer rather than an investor of BTC...)
Not your wallet that matters in this regard, what matters are your backup, your seed phrase or private key can recover back your wallet even on other side wallet devices.