I think that you've got the basic idea. The general idea is to compute a surface as the difference between the river's level and the surrounding terrain, with an area of effect proportional to the flow. Then apply an exponent (or blur, or averaging operation) to that map and blend it back to the original surface. It looks like you have something similar in the river width calculation, but what I'm suggesting would go a bit farther and should result in a little less chiseled canyon walls.