Queue system to fairly (round robin, etc) process messages from multiple clients

I have a simple RabbitMQ single queue serving multiple servers that process time consuming messages. The servers work together in a swarm to process messages and clear this single queue.

Client A on the front end starts a job. Each job consists of 1,000+ messages which go into the single queue and are processed by about 12 servers. It takes the 12 servers about 10 minutes to process all 1,000+ messages from Client A

My problem is if client B connects to my site and starts a job. His messages go into the stack behind Client A's 1,000+ messages already in queue. This causes Client B to have to wait till ALL 1,000+ messages of Client A problem to be processed before any of Client B messages are processed.

I need a way for my servers to see both Client A and Client B messages and when a server finishes a message, to select from either Client A or Client B either at random or in some other manner such that some balancing occurs, allowing Client A and Client B messages to be processed somewhat concurrently even through Client B messages came in much later after Client A messages were already in the queue.

I looked into Routing, but it's a bit tricky because I don't want to preordain servers to process only a specific client's messages, nor do I even know how many clients there will be. I also want it to be flexible, if there is only one client, all servers should process that client's messages at full speed, until a time that another client shows up.

The only thing I can think of is each new Client spawns its own unique rabbitmq queue upon inception. Then somehow this dynamic number of queues feeds a single queue in a round robin fashion. The servers then read from this single queue which has a nice mix of clients.

Your workers should each have their own queue from which they consume messages that announce new "User" queues. These worker queues would be bound to a fanout exchange. Then, when your Public Api creates a "User" queue and publishes messages to it, it also sends a "New User Queue" message to the fanout exchange, and every worker would be alerted to the new "User" queue. If all workers consume from the "User" queue with an appropriate prefetch/qos value, the messages will be round-robin delivered as you expect to them.