Yes, it is possible; not trivial, but possible:
(I will add some explanation when I have time)
\documentclass{beamer}
\usepackage{totcount}
\usepackage{tikz}
\regtotcounter{section}
\newcounter{vertrules}
\setbeamercolor{section in head/foot}{fg=green!40!black}
\setbeamercolor*{frametitle}{fg=green!40!black}
\setbeamercolor{myheadline}{fg=green!40!black,bg=green!10}
\setbeamertemplate{headline}
{%
\begin{beamercolorbox}[wd=\paperwidth]{myheadline}
\vskip1.5ex%
\insertsectionnavigationhorizontal{\paperwidth}{\hskip0pt}{\hskip-12pt}\vskip2pt
\end{beamercolorbox}%
\setcounter{vertrules}{\totvalue{section}}
\ifnum\thevertrules<2 \else
\addtocounter{vertrules}{-1}
\begin{tikzpicture}[remember picture,overlay]
\foreach \i in {1,2,...,\thevertrules}
\draw[ultra thick,green!40!black] (\i*\sectionboxwd+0.5\i,0) -- (\i*\sectionboxwd+0.5\i,1);
\end{tikzpicture}%
\fi%
}
\setbeamertemplate{section in head/foot}{%
\hspace*{-6pt}\setlength\fboxsep{0pt}%
\parbox[c][4ex][t]{\dimexpr\sectionboxwd-5pt\relax}{%
\hfill\parbox{\dimexpr\sectionboxwd-12pt\relax}{%
\raggedright\insertsectionhead%
}\hfill\mbox{}%
}\hspace*{6pt}%
}
\newlength\sectionboxwd
\AtBeginDocument{%
\ifnum\totvalue{section}>0
\setlength\sectionboxwd{\dimexpr\paperwidth/\totvalue{section}\relax}
\else
\setlength\sectionboxwd{\paperwidth}
\fi
}
\begin{document}
\section{Test Section One with a really long title}
\begin{frame}\frametitle{Test frame one}test\end{frame}
\section{Test Section Two}
\begin{frame}\frametitle{Test frame two}test\end{frame}
\section{Test Section Three}
\begin{frame}\frametitle{Test frame three}test\end{frame}
\section{Test Section Four}
\begin{frame}\frametitle{Test frame four}test\end{frame}
\end{document}
And some images showing the result with the vertical rules:



