So I just recently found out that 2^261 bytes can theoretically be stored on the Ethereum Blockchain. So this means 2^256 key-value mappings. My question is, what is the gas cost per NEW key-value mapping? (instantiation only). Then how much would it cost to store the theoretical maximum of data?
A mapping instantiation doesn't cost anything. We can say it exits with all their values initialized to zero bytes. You only pay for storage changes, for example when assigning a value to an entry.
Writing a non-zero value to a 32 bytes storage slot costs 20000 gas. As of 2021-10-22 17:00 UTC with a gasPrice of 80 gwei writing the entire mapping will cost 2^256 * 20000 * 80 / 10^9 = 1.85 x 10^74 ethers.