"Even if there was a separate OS running in parallel with Android, how could it access the wireless-networks-based and satellite-based location data? I thought that access to these things is controlled by Android."
There is a separate OS running in parallel with Android and it is running on the very hardware that makes the network connections to the cellular network that you are speaking of.
In fact there are two - the OS and software stack that run on the baseband processor and the OS and software (java apps) that run on your SIM card, which is a full blown computer with its own memory and processor, etc. In fact, your carrier can upload new java programs to your SIM card without your knowledge at any time.
Your final question is a good one - many (most ?) implementations give the baseband processor DMA to the main, application processor. So you are hopelessly owned. Deeply, profoundly, hopelessly owned.