So, we've been talking about the list of New Pages as a queue. People either work from the front or the back of the queue, as it were. I want to step outside of that thinking and propose a different system because there are several problems with it (not the least of which being that people edit conflict each other when working on the same side of the queue).
Let us instead think of putting new pages into a "stack". This is programmer terminology, so I'm loathe to use it, but it's a more accurate term. A "queue" is a stack, but it's got a specified direction: "First in, first out" (FIFO), or "Last in, first out" (LIFO). Currently, patrolling from the front of the queue is a FIFO process, and patrolling from the back is a LIFO process.
We don't have to be bound by this idea. We can create unique stacks per user. We can also do things like "filter by categories" or other metadata that might be easy to pick up (and, in the future, with better metadata tags, get even fancier). Unique stacks would also help to alleviate edit conflicts and double patrolling.
Consider a system like the following:
Say that there are 1,000 articles in the total queue. They are (naturally) ordered by creation date. We have five people who start "Patrolling".
For each of those five people, the system will randomly select 20 articles from the entire queue, shuffle the order, and then present them to the Patroller. No two people will get the same articles as long as they are in the same "patrolling session". So if I start a session, the system may assign me articles #45 as part of my personal stack. As long as I'm in the session, no one else will be assigned article #45. If I end the session, or close it, or skip #45, it will be put back into the main pool and can be assigned to someone else.
It's like a deck of cards. Currently, we only ever see the cards in order: AH, 2H, 3H, 4H, 5H, etc. Let us instead shuffle the deck. When you deal hands in poker, no two people will ever have the same cards (unless, you know, someone is cheating). Further, we're guaranteed a more equitable distribution of attention across the entire queue.
Patrollers could still choose to focus on the front or the back (FIFO, LIFO), obviously. They could also create "stacks" based around categories or namespaces. It may be possible to do stack creation based around WikiProject but I think that's too much to hope for.