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.
Update (Dec, 2021): Since EIP1559, the account must hold ETH to pay the fee at the time it is included in the block, and most of this ETH is burned (disappearing, to the benefit of anyone holding ETH whose ETH become proportionally more valuable) rather than being given to the miner. It is still technically possible for a miner to include a transaction from an account with no ETH at the time of sending, but they will have to add a transaction before it crediting the account with the ETH required to pay the fee.