Would it not suffice to just make the singletons "immortal"?

Without affecting the hotpaths that are Py_INCREF and Py_DECREF, changing _Py_Dealloc to test for objects with a "special" destructor could be used:

    destructor dealloc = Py_TYPE(op)->tp_dealloc;
    if (dealloc == _Py_SingletonSentinel) {
        /* reset refcnt so as to not return here too often */
        op->ob_refcnt = PY_SSIZE_T_MAX;
    }
    else {
        (*dealloc)(op);
    }

Even in the presence of multiple mutating threads, the object cannot be destroyed.  Worst case, they all call _Py_Dealloc.