The term "wallet" can be used in many different ways, but most commonly it is used to refer to interface or application to manage an account or address, such as MyCrypto or MetaMask. With a wallet, you can generate a private key (or mnemonic phrase, keystore file, etc.), and use the software to send transactions and sign messages.
Cryptocurrency is basically a form of cashless money. It does not have to be stored. Instead, balances of all accounts have to be recorded somewhere and all participants need to agree on what current balances are.
Ethereum uses sophisticated cryptography algorithms to allow honest participants to agree on current balances without knowing nor trusting each ...
Transactions from an exchange are usually sent from a "hot wallet", basically a wallet that is managed by the exchange. Most of the time exchanges pay for the gas, so you don't need any ETH in the exchange to withdraw tokens.
In the case of a decentralised exchange (DEX), you do need some ETH, since those kinds of exchanges are based on a smart contract.