I have a contract where the user has to interact twice.
Is it possible to deposit GAS and store it in the contract for the first interaction, so the later interaction will be "free"? (and additional gas will be refunded to the user).
This isn't directly possible, but GasToken roughly does this by storing data and then deleting it later to claim a gas refund. But it's impossible to get the transaction fee down to zero, because gas refunds can only offset up to half of the transaction fee.
Note that you can also use some form of relayer to pay gas on behalf of a user. (Search for "meta transactions" for common patterns.) So a user could pay ether up front that is later used to reimburse relayers who pay for gas on future transactions.
What you can do is sending some slice of ether you charge on the contract before the second transaction to reimburse the user of gas cost. With all the limitations derived from fluctuating gas price, accounting in the contract and so on.