Transactions with many small outputs could be censored outright, what constitutes a "small output" could be revised later one, or computed automatically based on transactions accepted since N blocks.
While BTC can support infinite subdivision and that may come useful in the future, that infinite subdivision serves no purpose right now, or in the next few years.

Transactions where the same output address appears multiple times could be banned as well (as they only bloat the blockchain)

Changing the fee structure rather than just raising the fee would be also a possibility, so that you pay more for larger blocks with small amounts. LTC has something like that, and there were many proposals in that direction for BTC as well.
Like the above, the notion of "small amount" could be adjusted down the road.

Finally in the spam, there are some non-spendable script outputs, these have other uses, but are using the blockchain as storage, and thus could be asked a proportionally higher fee based on byte length.