OK, let's go back to the "__namespace__" idea, then. 

A long time ago I had the idea that the ast compiler could remember the list of "named blocks" (classes, functions) with their line numbers;
for example, the statement "class C" spans from line 20 to 40, "def foo()" spans from line 26 to 30.
Then, it's easy to locate the function "C.foo" if you only have its co_firstlineno.  This would also be a replacement for the awful hacks in Lib/trace.py::file_module_function_of() (please read the code and say "aaargh!").
This information would be stored in the module itself, and probably compressed with techniques similar to co_lnotab.