I have definitely worked on Python projects in the past that were easily parallisable and worked absoluately fine. I simply created threads with threading.Thread, passed messages around with queue.Queue and used some standard Python modules to process those messages. The messages were independent enough from each other that I didn't have any issues with marshalling access to them, while being large enough that the overhead of mulithreading was still outweighed by its benefits. Rewriting the whole thing in C++ (etc.) would have made negligable difference to performance.
I can certainly imagine a program similar to what you describe, where there are lots of messages that operate on a single monolythic data structure, which couldn't easily be made to work with true parallelisation in Python.
You probably do not want to do that in the first place. The reason that the GIL still exists is that the overhead of fine-grained locking for Python datastructures would negate the speedup from multithreading.
Other language (like GoLang) do support parallelism but they have a more advanced runtime and don't use a GIL.
In the case of Python, the single-threaded implementation was already there, the implementation that removed the GIL in favor of fine-grained locking failed to deliver the goods.
If you want to actually take advantage of parallelism, you want data structures that are amenable to it, which is basically sections of arrays without a lot of potential read/write conflicts over multiple threads. If you're at that point, you probably want to use C/C++/Rust anyway, you don't want speed up something that's already 100x slower (the interpreter) by parallelizing it. Python offers that with C-extensions like NumPy.
Not if you're reading most of the time and are using a modern concurrent GC.