It would be better discuss such ideas on python-ideas mailing list (http://mail.python.org/mailman/listinfo/python-ideas).

Option 3 breaks existing code such as

    for k, v in d.items():
        if pred(k, v):
            d[k] = newvalue
            break

Option 1 is memory inefficient. It requires a list of iterators in every dict (well, in almost every dict). And it doesn't look more time efficient than option 2.

Implementation of option 2 was provided and rejected in issue19332.