Here's another idea: have a new type field (a tp_something) that exposes the GC priority for this type.  It could be an integer between -8 and 7, for example (0 being the default).  Then tp_finalize would be called in sorted priority order.

The tricky part of course is to make this acceptable performance-wise (i.e. avoid walking the collectable list 16 times, once for each priority level).  For example by creating bucket lists for each priority level (only for objects with a non-NULL tp_finalize).