They say the wallet is stored on the blockchain. When you create a wallet, there are no fees. Who pays for this?
Whoever said that has a misunderstanding of what a wallet is. Wallets are not stored on the blockchain, they are stored on your local machine or with the service you are using. In the case of electrum (you posted in the electrum sub after all) the wallet file is stored on your local machine.
You can recover your wallet from the 12 word seed. If you have nothing, you can retrieve your wallet from the 12 word seed. When you receive this wallet there is no password on it. It is all instantaneous, thus how can it be on the blockchain if there is no fee?
Your address IS NOT stored on the blockchain. The blockchain is merely a ledger which contains all the transactions that has occurred since the start of Bitcoin. The address generation does not involve the blockchain.
The 12 word seeds generates a list of addresses which users can send Bitcoins to. When you spend the Bitcoin, your transaction is relayed onto the Electrum server, relayed to the Bitcoin Full nodes and the full nodes will look at their Blockchain to find an unspent output the transaction used. If they can find the unspent output, the transaction is valid. Full nodes operators are not paid for this.
If you create a electrum wallet, send 5 bitcoins to it. Send 2 btc to someone, then delete the wallet. You can then retreive your wallet immediately on another computer.
To try to make the question more clear say you have a fresh install of windows. You download electrum and retrieve your wallet with 12 words. Suppose you have 100s of transactions. Where did you wallet retrieve from? It can't be bitcoin blockchain since no fees were paid and it is all instantaneous. You might have retrieved 1000 bytes of info from 60 bytes of words.
Electrum servers, which are backed by Bitcoin full nodes. The Electrum server indexes all the transactions and acts a little bit like a Bitcoin full node, which can supply information such as transaction information and broadcast transactions sent from the Electrum client.
Electrum generates your addresses and query Electrum server for Bitcoin blockchain information such as the list of transaction that has occurred, current block height etc.
Lets talk about the actual Bitcoin since your question now is mainly about how can the information about an address be found without any fee. For Bitcoin Core, they download a copy of the Blockchain from another full node. As the client synchronize, the client searches the Blockchain for transactions related to the wallet.
For example:
If your address is 1ABCD
1ABC sent 1 BTC to 1ABCD =1BTC Balance
1COM sent 0.5BTC to 1ABCD= 1.5BTC Balance
1ABCD sent 1 BTC to 1ORG = 0.5BTC Balance.
Hence, your final balance is 0.5BTC.
These transactions are available on the Bitcoin Blockchain and this is how all the transactions about the wallet is found. Addresses are not stored on the Blockchain, but rather the transactions are. Your client merely uses the Blockchain to get any information about your address.