It seems to me that the option of going with a tracing garbage collector is preferable. Removing the GIL will require a lot of changes anyway, and it may be better to go all they way so as to preserve performance. It would affect the C API and extensions modules would have to be reworked for this, but on the other hand you avoid all the issues with reference counting. If extension modules rely on code generation, such as Cython, a move to a radically different C API might be less painful than expected.
From what I know, most current managed languages are using GC, not reference counting, so perhaps it's an inherently better approach.