There could be a LaTeX package to do this for you, but I'm more of a TeX person, so I tried to come up with a TeX solution (not always the best idea to mix plain TeX with LaTeX but I think I have it working).
Try this. Box 255 is the box register that TeX places the page contents into before the page is output. What I've done is taken the existing output routine, and changed it to insert into box 255: a 0-height, 0-width infinitely shrinkable-but-overflowing set of boxes containing a rule that is the height of the page, 0.4pt thick and with any luck, half an inch away into the left. The existing contents of box 255 is then added after this rule. Then I call the previous output routine which outputs the page (which now includes a rule), and also the headers and footers.
\newtoks\oldoutput
\oldoutput=\expandafter{\the\output}%
\output{%
\setbox255\vbox to 0pt{%
\hbox to 0pt{%
\vsize\ht255%
\vbox to \ht255{%
\vss
\hbox to -0.5in{%
\hss
\vrule height \ht255 width 0.4pt%
}%
}\hss
}\vss
\box255%
}%
\the\oldoutput
}%
Put it before your \begin{document}
command. This might not solve your problem completely, but hopefully it should get you started. Here's a great page for learning about TeX primitives and built-in things.