How can I make my classes usable as dict keys?

The answer is yes, you need to redefine __hash__() and __eq__():

>>> class A(object):
...   def __init__(self, data=''):
...     self.data = data
...   def __eq__(self, another):
...     return hasattr(another, 'data') and self.data == another.data
...   def __hash__(self):
...     return hash(self.data)
... 
>>> a1, a2, a3 = A('foo'), A('foo'), A('bar')
>>> d = {a1: 'foo'}
>>> d[a1]
'foo'
>>> d[a2]
'foo'
>>> d[a3]
Traceback (most recent call last):
  File "", line 1, in 
KeyError: __main__.A object at 0x927d0>

As explained in another comment default implementation of __hash__ is just simple identity, so if you want to make it more sophisticated, you need to define it explicitly.

What you did should work, as long as you don't override the __hash__() and __eq__() methods. It will use object identity as equality. If you want a different notion of equality, you can override the __hash__() and __eq__() methods of your class.