We can use this answer on math.SE to determine on which side of a line a point lies. Based on this formula, we have that the new gray level is given by
f[{{x1_, y1_}, {x2_, y2_}}][gl_, {x_, y_}] := gl + 0.1 Sign[(x - x1) (y2 - y1) - (y - y1) (x2 - x1)]
We can apply this to all pixels recursively in the following manner:
iterate[img_] := Module[{dimx, dimy, pts},
{dimx, dimy} = ImageDimensions[img];
pts = {RandomInteger[dimx, 2], RandomInteger[dimy, 2]};
ImageApplyIndexed[f[pts], img]
]
img = ConstantImage[0.5, {300, 300}];
Nest[iterate, img, 50]
I'm actually not sure how to show that this works as it should, so if anyone spots an error please tell me.