Hmm. So let's say we assign every trader a unique ID and randomly (or not) prioritize the IDs every tick. (I'm assuming you're shuffling the IDs and not the individual orders; otherwise, as jsnell points out, it averages out to the pro rata case.) The main problem I can see is that if someone can get their hands on multiple IDs, they can duplicate their orders across all their IDs and we're back to the pro rata system.

Even if you make sure to assign just one ID per trading firm, firms could coordinate to share their IDs. For example, if you're not using your ID this tick, you might place an order on my behalf for a small fee. And I'll also have sent some of my orders through an independent broker to take advantage of their ID. (Of course, if that broker places many such orders, and only some of those fill, they'll need some policy for which of their customers get the trades... maybe they could use time priority?)

It's conceivable (if unlikely) that the SEC could enact and enforce a ban on such collusion. Even then I think there would be other perverse incentives, but I'll need to think more about it.