There's a technique which I call 'lazy popping' which can help here.

The idea is that you don't delete immediately from the queue. Rather, you leave deleted items in the queue, but mark them as deleted in another data structure -- usually a set. Whenever you have to pop an item to execute, keep popping until you reach an item that hasn't yet been deleted.

This gives you constant-time push, amortized constant-time pop (although you may pop multiple deleted items off the queue each time you pop an item to execute, each item only gets popped exactly once) , and constant-time deletion, which is better than what you can get by maintaining a list and deleting from start or middle.

In this case, you'd save the IDs of deleted items in the set. It looks like this (untested code):

import collections

class DeletableQueue:
    def __init__(self):
        self.deleted = set()
        self.queue = collections.deque()
    def push(self, item):
        self.queue.append(item)
    def pop(self):
        # Precondition: there is at least one non-deleted item on the queue.
        while id(q[0]) in deleted:
            q[0].pop_left()  # Discard an already-deleted item.
        return q.pop_left()  # Return the actual item to pop
    def delete(self, item_to_delete):
        self.deleted.add(id(item_to_delete))