The PowerVR SGX platform, for example, supports 8 texture units (TEXTURE0...TEXTURE7), which can be accessed directly without shaders.
Using texture combiners, I can access values from the previous texture stage (GL_PREVIOUS) or the currently bound texture (GL_TEXTURE), etc. Is there a way to access anything from any stage before the immediately-previous one?
E.g. if I want to set up essentially multiple independent threads of processing and then combine the ultimate result for output, is this possible? Or am I restricted to flowing data from n to n+1 only?
No, the flow is restricted from n to n+1. The Combiner API hasn't been touched in years, it's modern replacement (Shaders) are much more flexible.