They're a free marketing channel for celebrities (and businesses) with large follower count. They monetize those users indirectly by showing them ads of course. But a case can be made to charge some money from the celebrities themselves for value add services (e.g., personal customer service, subtle advantages in placement of tweets in user's streams etc. Lots of these tweeple/tweepanies would be willing to pay, say $20 a month for value added services leading to better engagement.
There's also a really interesting monetization model of users rewarding each other for exceptional posts with virtual goods. Reddit gold seems to be a successful example of this model. Twitter is a public square just like reddit. They should try this model.
This is probably closer to a viable revenue model. Don't charge per-tweet, rather charge people who have a large follower count to broadcast a tweet to all of their followers. Free tweets go to the top X% or 1000 followers, whichever is greater, and to truly broadcast to a million followers costs money. Something similar to what FB does for posts from pages that you once, in the distant past, liked; page owners complain about this to no end, but they keep paying...
That would break the followers expectations that when I follow someone I expect to get their tweets. Facebook is already pulling this crud and it's annoying.
It doesn't even have to be a "not deliver" model. It can simply be a matter of "deliver harder" for paying celebs/companies. Not as hard as a promoted tweet but not as ignorable as just a regular tweet scrolling past the bottom edge of the screen. There can be special pricing for highlighting tweets or "temporal persistence" of tweets.
There's also a really interesting monetization model of users rewarding each other for exceptional posts with virtual goods. Reddit gold seems to be a successful example of this model. Twitter is a public square just like reddit. They should try this model.