Ack, I didn't know you were working on this, too! I'm attaching my own atexit implementation; the patch includes changes to Modules/Setup, test_atexit and test___all__ so that the test suite passes.

One thing I'm not sure about is that I've moved call_ll_exitfuncs() up in the order of Py_Finalize(). This was necessary to make PyThreadState_GET() stop complaining about "no current thread" when calling the atexit functions at interpreter-shutdown, but I don't know enough to be sure that this change doesn't alter some assumption about finalization order. It looks alright to me, and "make test" passes, but I'd appreciate it if someone could look over that part.
File Added: atexit.patch