I have been trying to argue, though I feel a bit muddled at times, that the proxy approach eliminates the need for rexec and makes it possible to build a "restricted environment" without relying on the rexec code in the interpreter.
There's one rexec-related feature that you'll need to use though: that all built-ins (including __import__) are loaded from the __builtins__ variable in the globals, and that there's no way to get access to the default __builtins__ (assuming the restricted builtins override __import__ with something that won't let you import the real sys module, etc.). I mention this because this is actually a larger part of the restricted execution code than the restrictions on certain introspections that are also part of it. The latter are clearly not enough, and perhaps we should drop them (*requiring* proxies or capabilities to implement the rexec module, rather than the old and wounded Bastion [see Samuele's posts]). But the former (the treatment of __builtins__) is essential.
Perhaps mostly unrelated, I'll also note something about proxy implementation. Assuming proxies are instances of a type proxy, that type must derive from a type object. This means that if p is a proxy, object.__getattribute__(p, 'foo') is valid. It will take some very careful analysis to prove that this cannot circumvent the proxy's safeguards. (I believe Zope's proxies are safe.)
--Guido van Rossum (home page: http://www.python.org/%7Eguido/)