ERC20 Tokens – Paying Transaction Fees with Tokens

The default answer would be: No, you cannot use an account without Ether for anything related to the Fancycoin, as any interaction with a standard token requires a transaction which you need to sign and broadcast to the network and conversely pay for the transaction costs in Ether (at least for the time being you can only pay fees in Ether).

The more interesting answer is: Yes, by changing the requirements somewhat. You do sign a transaction off-chain, send it to someone else (e.g. by means of a pigeon, snail mail, or smoke signals). That someone else might then be able to send that transaction and potentially get a little reward for doing so.

The above idea is not all ironed (indicated security issues remain) but the following sketch works, I just tested it in Remix with a little help of the geth web3 console:

pragma solidity ^0.4.13;

/*
Author: Dr. Sebastian C. Buergel for Validity Labs AG
License: MIT

aim:
allow account without ETH but in possession of tokens to transfer tokens

approach:
sign message off-chain, send to other user, incentivize that user to broadcast message and get token as reward

remaining issues and solutions:
- replay protection (use nonce),
- frontrunning by other nodes (commit-reveal),
- timeout (expiry time)

step 0: choose amount, recipient (to), and reward (in tokens) for broadcaster
step 1: obtain hash from `calcHash` (off-chain, offline)
step 2: sign hash (off-chain, offline), e.g. using geth web3 console:
var signature = web3.eth.sign(web3.eth.accounts[0], hash);
var r = signature.substring(0,66);
var s = '0x' + signature.substring(66,130);
var v = '0x' + signature.substring(130,132); // make sure it is 27 or 28, else add 27

step 3: send transaction to someone else
step 4: that other account broadcasts the message by sending it to `broadcast`, funds get transferred and broadcaster gets reward
*/

contract Fancycoin {

    event Transfer(address indexed _from, address indexed _to, uint256 _value);

    mapping(address => uint) public balanceOf;

    uint public totalSupply;

    constructor(uint supply) {
        totalSupply = supply;
        balanceOf[msg.sender] = supply;
    }

    function transfer(address _to, uint256 _value) returns (bool success) {
        return transferFromTo(msg.sender, _to, _value);
    }

    function transferFromTo(address _from, address _to, uint _value) internal returns (bool success) {
        if (balanceOf[_from] >= _value && _value > 0) {
            balanceOf[_from] -= _value;
            balanceOf[_to] += _value;
            Transfer(_from, _to, _value);
            return true;
        } else { return false; }
    }

    // helper function since web3.sha3 is not (yet) able to concatenate arguments in the same way that solidity does it
    function calcHash(uint amount, address to, uint reward) constant returns (bytes32) {
        return sha3(amount, to, reward);
    }

    function verify(uint amount, address to, uint reward, uint8 v, bytes32 r, bytes32 s) constant returns(address) {
        bytes memory prefix = "\x19Ethereum Signed Message:\n32";
        bytes32 prefixedHash = sha3(prefix, sha3(amount, to, reward));
        return ecrecover(prefixedHash, v, r, s);
    }

    function broadcast(uint amount, address to, uint reward, uint8 v, bytes32 r, bytes32 s) {
        address sender = verify(amount, to, reward, v, r, s);
        assert(transferFromTo(sender, msg.sender, reward));
        assert(transferFromTo(sender, to, amount));
    }

}

Transaction fee on Ethereum is called Gas and is paid to the miners for the processing power they spent on the function call, here being ERC20 transfer(). Tokens on miner's level don't have any value and does not mean anything, rather than just a state change in a smart contract. Gas can only be the same coin/token that the blockchain is using to incentivize the miners, so here on Ethereum blockchain Gas is Ether.

To understand more of this concept you can read here: https://ethereum.stackexchange.com/a/62/3157