In the PEP3100 [1] there's written, in the "to be removed" list:
  "callable(): just use hasattr(x, '__call__') (?) [2] [done]"
and the note refers to a pdf [2] that instead says:
  "callable(): just call it, already"

If callable() was removed to encourage the EAFP [3] style, replacing "if
callable(x):" with "if hasattr(x, '__call__'):" is just a less-accurate
and less-readable way of doing the same (wrong) thing [4] (also note the
(?) next to the hasattr() expression).

This might be OK for automated tools like 2to3, but not for the doc and
the warning. Humans should probably replace the expression with a
try/except instead of using hasattr().
Even for 2to3 there are better and more accurate solutions though, like
the one proposed by the OP (not really readable) and isinstance(x,
collections.Callable).

(Note: what the OP said is correct for new-style classes, for old-style
classes callable() and hasattr() have the same result).

[1]: http://www.python.org/dev/peps/pep-3100/
[2]: Python Regrets:
http://www.python.org/doc/essays/ppt/regrets/PythonRegrets.pdf
[3]: http://docs.python.org/glossary.html#term-eafp
[4]: http://docs.python.org/glossary.html#term-lbyl