This won't be changed.  The dict type doesn't support efficient random choice (neither do sets, by the way), and it's been repeatedly decided that it would do a disservice to users to hide that.  As you know, you can materialize the keys in a list (or tuple) first if you _want_ to pay that cost.  Otherwise you should use a different data structure.

Note that there's really no differnce between Pythons 2 and 3 here.  If you _happen_ to have a dict that uses little integers as keys, then it can _appear_ to work, when a random integer picked from range(len(the_dict)) happens to be one of the keys.  But then you get back the associated dict value, not the key.  For example, here under Python 2.7.11:

>>> import random
>>> random.choice({0: "a", 1: "b"})
'b'
>>> random.choice({0: "a", 1: "b"})
'b'
>>> random.choice({0: "a", 1: "b"})
'a'

But if the keys don't happen to be little integers, it always fails:

>>> random.choice({"a": 1, "b": 2})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python27\lib\random.py", line 275, in choice
    return seq[int(self.random() * len(seq))]  # raises IndexError if seq is empty
KeyError: 1