Here's a possible solution; the idea is to have two auxiliary commands \prevsection and \nextsection to hold the names of the previous and next section to the current section; those commands will be used in the headline template to display the required information instead of the usual navigation bar.
The updating of \prevsection, \nextsection is done internally using a redefinition of \beamer@section.
All that you have to do is to fill in the mandatory argument for the commands \sectioni, \sectionii, ... ,\sectionviii with the information to be displayed in the navigation bar.
\documentclass{beamer}
\usetheme{Warsaw}
\newcounter{prevsection}
\newcounter{nextsection}
\newcommand\prevsection{}
\newcommand\nextsection{}
\makeatletter
\long\def\beamer@section[#1]#2{%
\beamer@savemode%
\mode<all>%
\ifbeamer@inlecture%
\refstepcounter{section}%
\beamer@ifempty{#2}%
{\long\def\secname{#1}\long\def\lastsection{#1}}%
{\global\advance\beamer@tocsectionnumber by 1\relax%
\long\def\secname{#2}%
\long\def\lastsection{#1}%
\addtocontents{toc}{\protect\beamer@sectionintoc{\the\c@section}{#2}{\the\c@page}{\the\c@part}%
{\the\beamer@tocsectionnumber}}}%
{\let\\=\relax\xdef\sectionlink{{Navigation\the\c@page}{\noexpand\secname}}}%
\beamer@tempcount=\c@page\advance\beamer@tempcount by -1%
\beamer@ifempty{#1}{}{%
\addtocontents{nav}{\protect\headcommand{\protect\sectionentry{\the\c@section}{#1}{\the\c@page}{\secname}{\the\c@part}}}%
\addtocontents{nav}{\protect\headcommand{\protect\beamer@sectionpages{\the\beamer@sectionstartpage}{\the\beamer@tempcount}}}%
\addtocontents{nav}{\protect\headcommand{\protect\beamer@subsectionpages{\the\beamer@subsectionstartpage}{\the\beamer@tempcount}}}%
}%
\beamer@sectionstartpage=\c@page%
\beamer@subsectionstartpage=\c@page%
\def\insertsection{\expandafter\hyperlink\sectionlink}%
\def\insertsubsection{}%
\def\insertsubsubsection{}%
\def\insertsectionhead{\hyperlink{Navigation\the\c@page}{#1}}%
\def\insertsubsectionhead{}%
\def\insertsubsubsectionhead{}%
\def\lastsubsection{}%
\Hy@writebookmark{\the\c@section}{\secname}{Outline\the\c@part.\the\c@section}{2}{toc}%
\hyper@anchorstart{Outline\the\c@part.\the\c@section}\hyper@anchorend%
\beamer@ifempty{#2}{\beamer@atbeginsections}{\beamer@atbeginsection}%
\fi%
\beamer@resumemode
\setcounter{prevsection}{\thesection}%
\setcounter{nextsection}{\thesection}%
\addtocounter{prevsection}{-1}%
\gdef\prevsection{\csname section\romannumeral\theprevsection \endcsname}%
\addtocounter{nextsection}{1}%
\renewcommand\nextsection{\csname section\romannumeral\thenextsection \endcsname}%
}%
\setbeamertemplate{headline}
{%
\leavevmode%
\@tempdimb=2.4375ex%
\ifnum\beamer@subsectionmax<\beamer@sectionmax%
\multiply\@tempdimb by\beamer@sectionmax%
\else%
\multiply\@tempdimb by\beamer@subsectionmax%
\fi%
\ifdim\@tempdimb>0pt%
\advance\@tempdimb by 1.125ex%
\begin{beamercolorbox}[wd=.5\paperwidth,ht=\@tempdimb,right,rightskip=1em]{section in head/foot}%
\vbox to \@tempdimb{%
\ifnum\thesection=1 \else%
\vfill{\color{fg!40!bg}\prevsection}%
\fi%
\vfill\insertsectionhead%
\ifnum\thesection=\beamer@sectionmax \else%
\vfill{\color{fg!40!bg}\nextsection}%
\fi\vfill%
}%
\end{beamercolorbox}%
\begin{beamercolorbox}[wd=.5\paperwidth,ht=\@tempdimb]{subsection in head/foot}%
\vbox to\@tempdimb{\vfil\insertsubsectionnavigation{.5\paperwidth}\vfil}%
\end{beamercolorbox}%
\fi%
}%
\makeatother
% Here you put the names that will go in the navigation bar
\newcommand\sectioni{test one}
\newcommand\sectionii{test two}
\newcommand\sectioniii{test three}
\newcommand\sectioniv{test four}
\newcommand\sectionv{test five}
\newcommand\sectionvi{test six}
\newcommand\sectionvii{test seven}
\newcommand\sectionviii{test eight}
\begin{document}
\section{test one}
\begin{frame}test\end{frame}
\section{test two}
\begin{frame}test\end{frame}
\section{test three}
\begin{frame}test\end{frame}
\section{test four}
\begin{frame}test\end{frame}
\section{test five}
\begin{frame}test\end{frame}
\end{document}
Some images of the headlines:




