I really think the GIL is saving a bunch of poorly written multi-threaded C++ wrappers/libraries out there. If they remove it, a bunch of bugs will appear in other libraries that might not be Pythons fault.
In the unlocked case, one could use low-overhead tricks used for GC safepoints in some interpreters. One low-overhead technique is a dedicated memory page from which a single byte is read at the beginning at of every opcode dispatch, and you mark that page non-readable when you need to freeze all the threads executing in the interpreter. You'd then have the SIGSEGV handler block each faulting thread until the one thread returned from C. That's fairly heavy in the case it's used, but pretty light-weight if not used.