As far as I understand, one of the ERC20 token's features is that you can pay a transaction fee with it. In other words, you can send them without having Ether. I transferred REP tokens to the exchange and back without using Ether on that exchange so that works.
I suppose that fee goes to miners. Where else?
So someone creates a token that has no value at all, makes a transfer and pays a fee with it, then some miner gets it but he doesn't have any idea what it is.
It is not really true at the moment that you can pay fees in anything except ETH, although there is some discussion about changing this. The way things normally work, you have to pay the fee in ETH. When you sent REP to the exchange you probably used ETH in your own account to deposit tokens in the exchange, and the exchange would have paid for the transaction to send them back out.
In theory, since it's up to the miner whether they include your transaction, you could send a low or zero fee in ETH and have a separate arrangement with a miner where you would give them some ERC 20 token, or send them USD via PayPal, or FedEx them a chicken. This depends on the miner thinking what you are giving them is valuable and being prepared to accept it as payment. If you've sent them a chicken but they don't want one, or you've sent them an ERC 20 token that they've never heard of and don't consider valuable, you shouldn't expect them to mine your transaction.
Everytime you make a transaction on ethereum you need to pay a fee to the miner of the block that will calculate the result of your smart contract. While this might change in the future, for the moment fees can only be paid in ether and therefore all users of your tokens need it. Tokens in accounts with a balance smaller than the fee are stuck until the owner can pay for the necessary fee. But in some usecases, you might not want your users to think about ethereum, blockchain or how to obtain ether, so one possible approach would have your coin automatically refill the user balance as soon as it detects the balance is dangerously low.
The creator of the token may have set it up so the fee is paid in ETH under the hood, users are just not aware of it. Source
as an additional information, recently an opensource protocol(0x protocol) has been presented to enable free EC20 token treading over Ethereum blockchain. the white paper is available https://github.com/bellaj/Bitcoin_Ethereum_docs/blob/master/0x_white_paper.pdf
How it Works
0x protocol is a hybrid implementation of a few existing technologies, combining the off-chain functionality of state channels with on-chain settlement, which they refer to as “off-chain order relay with on-chain settlement” for making transactions. What does this mean? Orders are relayed off-chain and then settled on-chain, lowering the costs for market makers while simultaneously benefiting from the near-instantaneous settlement time of the Ethereum blockchain.
This is possible! Your service can take fees in your own tokens and pay fees for users in ETH in absolutely trustless and secure way. See this answer: https://ethereum.stackexchange.com/a/46546/3032
In this README you can found MyToken smart contract example, which transfer calls can be delegated to anyone (who will pay fees): https://github.com/bitclave/Feeless
TomoChain is implementing a protocol named TomoZ. It will help token holder can pay transaction fee by tokens.
In normal case:
Sender send tokens to receiver
Sender pay tx fee by native token (TOMO) to nodes
In TomoZ:
Sender send token to receiver
Sender send tx fee in token to Issuer
Issuer send tx fee in native token (TOMO) to nodes
