Queue that can sort by multiple priorities?
Simple solution: use two queues
If you want to keep track of multiple priorities that are unrelated then you'll have to use 2 priority queues.
You don't have to duplicate all the data, because you can just put a reference (pointer) to the data in your queue.
That way you only have 1 location where your object resides and two pointers to it in the two priority-queues.  

So the memory load would be $O(nk+2n)$ where $k$ is the length of your object and $n$ is the number of objects.
As long as $k$ is significantly long the $2n$ factor will be insignificant.  

Complex solution: intertwine the queues and use COW semantics
If the priorities are related, then you can lessen the memory load by implementing the priority queue as a linked structure where shared items link to the same node.
You'll have to use copy-on-write semantics on the shared nodes for this to work.  

For an example see B(+)Trees in databases
Something very similar happens in databases, where the tables are represented as B-trees.
When a change is made a reference to the tree is copied and copy-on-write is applied to all nodes that are changed.
When the change is committed the pointers for the changed tree and the original tree are exchanged.
While the transaction is in progress the old tree and the new tree are intertwined.  

Beware the running time of COW
You can do the same to your priority queue, but this only makes sense if most of the data will be the same for the queues or writes are rare, otherwise the copy-on-write semantics will kill your running time.