According to the example from the documentation, you can use tuples, and it will sort by the first element of the tuple:
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')
So if you don’t want to (or can’t?) do a __cmp__ method, you can manually extract your sorting key at push time.
Note that if the first elements in a pair of tuples are equal, further elements will be compared. If this is not what you want, you need to ensure that each first element is unique.