The trick here is to use the fancyhdr package which lets you customise the running heares and footers. You put what you want into the fancyfoot[LE] for the left footer on even (left) pages, and in [RO] for the right footer on odd (right) pages. The footer is only a fixed amount high, so you use \raisebox from the graphicx package to push it up .75\textheight; but TeX's page builder will complain that it's poking up beyond the wlloed height, so you enclose it in \smash, which is normally meant for breaking the height rules in formulas, but works here as well. Finally, use \llap and \rlap to push the resulting box outwards beyond the LH and RH margins. This example puts the page number in a box, but you could change \fbox{\thepage} to \somethingelse{\thepage} (like \uline if you use the ulem package).
\documentclass{book}
\usepackage{fancyhdr,graphicx}
\newlength{\rshift}
\setlength{\rshift}{\textwidth}
\addtolength{\rshift}{3pc}
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
\fancyfoot[LE]{\llap{\hbox to3pc{\smash{%
\raisebox{.75\textheight}{\fbox{\thepage}}}\hfil}}}
\fancyfoot[RO]{\null\rlap{\hbox to\rshift{\hfill\smash{%
\raisebox{.75\textheight}{\fbox{\thepage}}}\hfil}}}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\usepackage{lipsum}
\begin{document}
\section{stuff}
\lipsum
\end{document}
///Peter