Is there any way to avoid this low-value fee?Or to increase my priority?
The standard way is to send to multiple addresses in one large transaction instead of multiple tiny transactions (this is why sites like dailybitcoins.org have a payout delay - it allows them to accumulate payouts for multiple users and send them all in one transaction). You will still probably have to pay the anti-spam fee, but the fee per output will be much smaller on average (because you have more outputs per transaction).
You can, of course, modify the source code to send transactions with no fees at all, but these transactions are likely to take an extremely long time to get confirmed, and may never even get confirmed at all, causing your users to hate you (to put it mildly). This one falls squarely in the "don't do that" category, and I only mention it because you might be tempted to do it on your own, then get upset that nobody warned you it was a bad idea.
My concept is based on sending small amounts, but not in a spammy way..
Unfortunately, the only way to distinguish small amounts from spam is to include a transaction fee. Otherwise anyone could send small amounts to themselves repeatedly to bloat the blockchain, and nobody wants that. As a result, virtually no miners will process such transactions unless an appropriate fee is included.