Put your border in the header (even though outside the area normally used by a header) as a graphic. Use the different even and odd selection for your headers and footers to alternate them.
Header/Footer Settings Recap