however, even not knowing exactly how GPU's work, I can't believe this is a viable method.
No. This is method for CPU. On GPU you don't have:
- Free access read + write arrays (unless you are using CUDA or OpenCL)
- Infinite cycles
So you can't easy program algorithms like "find the first level at which the valley's slope is 0".
The only way to generate rivers on GPU - is a flow erosion simulation. And this is really powerful way, giving very realistic results. But it is extremely slow for now. You can watch erosion in real time, but only for one chunk of the terrain, and... in real time. This man what you must wait few minutes until erosion process reaching desired level. I don't remember links now, but you can google for "intractive GPU erosion simulation" or like this.