From your description, it's not clear (at least to me) which template you need to modify; headline or frametile. Anyways, you can use \addtobeamertemplate to add the spacing before (using the first argument) and after (using the second argument) the headline or frametitle template; a little example (of course, instead of 1cm you can use the desired length):
\documentclass{beamer}
\usetheme{Warsaw}
\addtobeamertemplate{frametitle}{\vspace*{1cm}}{\vspace*{1cm}}
\begin{document}
\begin{frame}
\frametitle{Test Frame}
test
\end{frame}
\end{document}

After the new requirement made in a comment, a redefinition of the frametitle template (as defined in beamerouterthemeshadow,sty since the theme used is Warsaw) is needed:
\documentclass{beamer}
\usetheme{Warsaw}
\makeatletter
\setbeamertemplate{frametitle}
{%
\nointerlineskip%
\vskip-2pt%
\hbox{\leavevmode
\advance\beamer@leftmargin by -12bp%
\advance\beamer@rightmargin by -12bp%
\beamer@tempdim=\textwidth%
\advance\beamer@tempdim by \beamer@leftmargin%
\advance\beamer@tempdim by \beamer@rightmargin%
\hskip-\Gm@lmargin\hbox{%
\setbox\beamer@tempbox=\hbox{\begin{minipage}[b]{\paperwidth}%
\vbox{}\vskip.50ex% NEW: original \vskip-.75ex
\leftskip0.3cm%
\rightskip0.3cm plus1fil\leavevmode
\insertframetitle%
\ifx\insertframesubtitle\@empty%
\strut\par%
\else
\par{\usebeamerfont*{framesubtitle}{\usebeamercolor[fg]{framesubtitle}\insertframesubtitle}\strut\par\vskip2ex}% NEW: added \vskip2ex
\fi%
\nointerlineskip
\vbox{}%
\end{minipage}}%
\beamer@tempdim=\ht\beamer@tempbox%
\advance\beamer@tempdim by 2pt%
\begin{pgfpicture}{0pt}{0pt}{\paperwidth}{\beamer@tempdim}
\usebeamercolor{frametitle right}
\pgfpathrectangle{\pgfpointorigin}{\pgfpoint{\paperwidth}{\beamer@tempdim}}
\pgfusepath{clip}
\pgftext[left,base]{\pgfuseshading{beamer@frametitleshade}}
\end{pgfpicture}
\hskip-\paperwidth%
\box\beamer@tempbox%
}%
\hskip-\Gm@rmargin%
}%
\nointerlineskip
\vskip-0.2pt
\hbox to\textwidth{\hskip-\Gm@lmargin\pgfuseshading{beamer@topshade}\hskip-\Gm@rmargin}
\vskip-2pt
}
\makeatother
\addtobeamertemplate{frametitle}{\vspace*{1cm}}{\vspace*{1cm}}
\begin{document}
\begin{frame}
\frametitle{Test Frame Title}
\framesubtitle{Test Frame Subtitle}
test
\end{frame}
\end{document}

The lines that were changed are signaled in the code with % NEW; there you can adjust the lengths according to your needs.