Does there not exist some ridiculously parallel equivalent of Bresenham or Wu? I imagine with the right datastructure you should be able to do pixel/line intersection tests in the pixel shader?
In order to reduce the overdraw to something manageable, you need to generate geometry (via the CPU, geometry shader or vertex shader) that covers a relatively small superset of the pixels you actually want to draw.
Sure—it's trivial. Draw some bounding geometry and calculate the Euclidean distance to the line in your fragment shader. Shade accordingly.
The trick is finding that minimal bounding geometry.