Custom implementation of python queue to use dict instead of dqueue
1. Review


There is no docstring for ChannelDict. The text in the post would make a good start.
A ChannelDict is not a dictionary (it doesn't support the mapping interface, __getitem__ and __setitem__ and so on), so the name is a bit misleading.
ChannelDict is not specialized for channels: it would work for any kind of object. A name like RandomQueue would make it easier for the reader to understand the purpose of the code.
ChannelDict inherits from queue.Queue but has a different interface for initialization (it takes an iterable of channels instead of a maximum size). Perhaps this is convenient for your use case but it makes the code a little harder to understand because you can't just say "it's just like a Queue except that it gets items in random order", you have to explain the difference in initialization and that you can't set a maximum size.
The algorithm for getting a random item from the queue takes time proportional to the number of items, because get_free_channels has to loop over all the items looking for any that are free.
ChannelStatuses.UNDERFUNDED is declared but not used.


2. Revised code

One way to efficiently pick a random item (instead of looping over all the items) is to keep the available items in a list, and to swap the randomly selected item with the last item in the list before popping the selected item.

from queue import Queue
from random import randrange

class RandomQueue(Queue):
    """Variant of Queue that retrieves items in a random order."""
    def _init(self, maxsize):
        self.queue = []

    def _qsize(self):
        return len(self.queue)

    def _put(self, item):
        self.queue.append(item)

    def _get(self):
        queue = self.queue
        i = randrange(len(queue))
        queue[i], queue[-1] = queue[-1], queue[i]
        return queue.pop()