Updateable Priority Queue
Your code looks good, there's not much for me to review, but here are a couple improvements/changes I would make.

Improvements


Docstrings: You should include a docstring at the beginning of every method/class/module you write. This will help any documentation catch what your code is supposed to accomplish.
If/Else: If you return a value in the if, then you don't need an else. You should just put the else code after the if, instead of inside an else, like so:


if key in self._entry_finder:
    return self._entry_finder[key]
else:
    raise KeyError('Item not found in the priority queue')


to

if key in self._entry_finder:
    return self._entry_finder[key]
raise KeyError('Item not found in the priority queue')


Updated Code

class UpdateableQueue:
    """ An updateable priority queue class """
    def __init__(self, iterable=None):
        self._heap = []
        self._entry_finder = {}
        if iterable:
            for item in iterable:
                self._entry_finder[item[0]] = item[1]
                heapq.heappush(self._heap, (item[1], item[0]))

    def __getitem__(self, key):
        """
        Returns the item with the specified key, if exists. Else,
        it raises a `KeyError` exception
        """
        if key in self._entry_finder:
            return self._entry_finder[key]
        raise KeyError('Item not found in the priority queue')

    def __len__(self):
        """ Returns the length of the queue """
        return len(self._entry_finder)

    def __contains__(self, key):
        """ Returns a boolean based on if the key is in the queue """
        return key in self._entry_finder

    def push(self, key, priority):
        """ Pushses a priority into the queue """
        self._entry_finder[key] = priority
        heapq.heappush(self._heap, (priority, key))

    def pop(self):
        """ Removes a priority from the queue """
        if not self._heap:
            raise IndexError("The heap is empty")

        value, key = self._heap[0]
        while key not in self or self._entry_finder[key] != value:
            heapq.heappop(self._heap)
            if not self._heap:
                raise IndexError("The heap is empty")
            value, key = self._heap[0]

        value, key = heapq.heappop(self._heap)
        del self._entry_finder[key]
        return key, value