https://github.com/python/cpython/pull/3640/files includes a more automated-tested-friendly version of Armin's deterministic reproducer (the generator loop uses range() to generator a separate loop counter, and then the test checks that the incremented closure variable matches that loop counter), together with a fix based on the idea of putting actual cell objects into frame.f_locals while a trace hook is running. It turned out a lot of the necessary machinery was already there, since CPython already uses a common pair of utility functions (map_to_dict/dict_to_map) to handle fast locals, cell variables, and nonlocal variables.

PEP 558 still needs another editing pass before I send it to python-dev,  and the PR needs some additional test cases to explicitly cover the expected locals() and frame.f_locals semantics at different scopes when a Python-level trace hook is installed, but I'm happy now that this is a reasonable and minimalistic way to resolve the original problem.