> This is exactly analogous to what you are seeing with __call__ and callable().

Your example is incorrect, __next__ is what makes an object iterable but not what makes an object have an iterator (what __iter__ does).

This correctly characterises the issue:

>>> class NonIter:
...     pass
...
>>> iter(NonIter())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'NonIter' object is not iterable
>>>
>>> class DynamicNonIter:
...     has_iter = False
...
...     @property
...     def __iter__(self):
...         if self.has_iter:
...             from functools import partial
...             return partial(iter, [1, 2, 3])
...         else:
...             raise AttributeError("Not really ...")
...
>>> dni = DynamicNonIter()
>>> iter(dni)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'DynamicNonIter' object is not iterable
>>> dni.has_iter = True
>>> iter(dni)
<list_iterator object at 0x000000000362FF60>

Now, if this is possible for `iter`, why shouldn't it be possible for `callable`? 

I'm not opposed to writing a PEP but the issue with `callable` is the only one I'm aware of, and this seems too small in scope anyway.