It is possible to transfer tokens to multiple addresses in a single Ethereum transaction using a smart contract.
This transaction is more expensive than a single transfer, but contains multiple, so the cost is shared and (hopefully) lower.
There are several dapps/websites that allow you to do that and the source code of such contracts is very simple (eg https://ethereum.stackexchange.com/questions/51513/doing-a-bulk-transaction-with-my-erc20-token-how-to-do-it)
(Note that many of these websites charge a fee on top, not needed by the network, I am not recommending using any one of them and will only use them in the Ropsten testnet for gas estimations)
Test results
New addresses (never received the token before)
- Single transaction: 51,794 gas
- Batch transaction: 7,106,669 gas for 250 -> 28,427 gas / transfer (-45%)
Existing addresses (received the token before, and have non-zero balance)
- Single transaction: 36,794 gas
- Batch transaction: 4,276,346 gas for 300 -> 14,254 gas / transfer (-61%)
It appears that adding multiple transfers in a batch reduces the transaction fees by around 50%.
I was honestly expecting a much larger difference (like 1/10th the cost), but 50% is not bad.
However, I don’t think this is a viable long term solution (considering how fast the fees changed in the last 2 months), as the fees would still be quite high even then.