[Ethereum] Can the total supply of a token be increased after deployment

The token standard doesn't require you to store balances in any particular structure - a public mapping is not part of the standard - so you can simply do this:

struct Account {
    uint balance;
    uint dividends;
}

mapping(address=>Account) accounts;

Assuming you give out dividends proportional to a user's token balances, though, updating the dividends is still going to be a lot of work. Fortunately, there's a better way:

uint totalSupply;
uint totalDividends;

struct Account {
    uint balance;
    uint lastTotalDividends;
}
mapping(address=>Account) accounts;

Now, when you want to give out dividends, increase totalDividends by the amount of the dividend. When a user wants to withdraw their portion of any dividends, they calculate (accounts[user].balance * (totalDividends - accounts[user].lastTotalDividends)) / totalSupply - that is, take the amount of dividend disbursed since they last checked, and calculate the fraction of it they should receive based on the percentage of the tokens they own. Then, update lastTotalDividends to the current value of totalDividends.

Note that if you're doing this, you need to prevent users from sending or receiving tokens until they've withdrawn their dividends, or else users could 'double dip' by transferring tokens between accounts. You could avoid this by adding another field to Account that tracks the dividends they're entitled to but haven't yet withdrawn, and updating that before a transfer out of or into an account.

So this option will require a decent bit of setup but it would indeed be the cheapest to do. You could create a payment channel of sorts by committing a large amount of tokens to a smart contract. You could setup the smart contract such that only permissioned addresses can request an airdrop. In order to request the airdrop they must submit a message signed by you.

This would be incredibly cheap as each user would pay the transaction cost of sending the coins themselves.

example (update):

Each user will be given a particular message h which is a combination of \x19Ethereum Signed Message\n32 + keccak256('user-address', 'airdrop-value') that you have signed, along with the signature parts vrs. When they post to your contract to withdraw their funds, they provide the necessary signature data (h,v,r,s), along with the values that make up message h to so that they can verify the unique message to them, but also verify that it was signed by you.

I recently had to figure this out myself and made a quick python program used to sign data and extract the necessary parts:

https://github.com/postables/Postables-Payment-Channel/blob/develop/python/signer.py