You create a contract that sends airdrops in batches and a helper script that submits the transactions.

Two days ago I was making some test transactions on 4000 addresses and it took exactly 42 minutes.