Is modifying a texture (painting on it) considered a "state change"? The convention in graphics is that performing fewer state changes is better than performing more state changes (switching shaders, binding buffers, binding textures, etc.). For textures, it is faster to render many polygons using a single atlas (for rendering sprites/text) than to individually bind a new texture for each polygon.

Does this hold true if I am continually painting to a texture via glTexSubImage2D? I have a stream of data coming in (over a network) that undergoes processing and is then painted to a texture one row at a time. The data is presented visually in an endless scroll.

Would I be better off painting to one texture rendered on one large rectangle (scrolling the painted data into view)? The idea here is that I would have one (or two) textures bound at any given time while I just continue to paint to it.

Or should I paint lots of little rectangles (only revealing the rectangle when painting is done)? I assume I would bind one texture per rectangle.
Updating an area of memory in the graphics device (a texture, buffer, and the like) is not quite the same as changing a rendering state. 

What makes a render state change expensive is the amount of work the driver has to do to validate the new state(s) and reorder the pipeline. This will most likely also incur some synchronization between CPU and graphics device. However, the amount of data transferred between the devices should be small for a state change (probably just a few commands).

For a texture/buffer update on the other hand, the main cost lies in the data transfer itself. In theory, unless you're reading the texture data back to the CPU after the update, there should be no synchronization or pipeline stalls. However, another aspect should be considered: API overhead. Even if the amount of data you're sending to the graphics device is small, if you do that often enough, eventually the cost of communicating with the driver/device will become greater then the cost of the data transfer. That's another reason why batching is so important when optimizing a renderer.

So in your case, the best approach, it seems to me, would be to keep a system-memory copy of the texture that you update whenever new data arrives. Set a dirty flag and consolidate as much updates as possible into one glTexSubImage for the whole texture (or a large sequential portion of it). You can also play with Pixel Buffer Objects and try to do asynchronous data transfer to reduce pipeline stalls as much as possible. If you can implement some kind of double buffering, then you can write to one copy of the texture while the other is being rendered with. This tutorial explores that scenario. That's my intuitive approach, I'd try to reduce the number of API calls and "batch" the texture updates. That being said, this is very speculative, and you'd have to profile and compare that to other approaches, like doing several small updates, to know for sure which is the most performant in your usage case.

As a side note, this presentation by NVidia is also relevant and provides a lot of good insights: Approaching Zero Driver Overhead in OpenGL.