Here's a sketch of possible non recursive deinit algorithm. The algorithm maintains a linked list of "to be deallocated" objects, the list is maintained via the "next" variable inside the object itself.
Initially deallocation list is empty. When an object with retainCount = 1 is released - it is pushed on top of deallocation list. Then the list is processed from top. We pop the top object from the list, we take all reference type properties of this object and look at them one by one right to left. If the property's retain count is greater than 1 we simply decrement it. If the property's retain count is 1 this object is pushed to deallocation list top. After we placed all object's properties on the deallocation list we start processing this list again, starting from top. We repeat this until deallocation list is empty.
If I am not mistaken deallocation order of this algorithm will match the current recursive deallocation order. If needed objects whose RC > 1 can also be released in the current left to right order, but that's probably not important.
As these are the objects being deallocated that are placed on the list, we can probably reuse 8 bytes of the object proper as the "next" variable, if that's possible the algorithm will not require additional per object memory. The issue left open - thread safety of the release list top variable.
Edit: if retain count is stored inside the object itself (is it now? I remember some global tables were used in the past) and if RC is pointer sized - RC itself can be reused as a pointer, as AFAIK there is no guarantee about RC of deallocated objects.
Edit 2: there's probably no issue with deallocation list top variable thread safety, as it can be maintained per "top level release call", even as a local stack variable. This algorithm internals won't call top level release. Separate top level invocations of release / deinit will effectively use different deallocation lists.