Gas is always paid by the people making the transaction. You can have a specific address full of tokens, with 0 gas. Someone sent them to you, he paid the gas for the transaction. If you want to send some of these tokens to someone, then you have to load this address with gas. If you don't have any, you have to buy some from an exchange.
I have heard for 0 gas transactions in this forum, but if they exist, I suppose you have to wait for days for the confirmation.
I'm seeing a lot of ICO's and they all have blockchain functionality in their plans. But the execution of a contract costs gas. If the users trade tokens, the gas is paid from the transaction cost. But if they simply store data in the blockchain, who pays the gas? Do they pay this from the money they raise in the ICO?