I have a solution that works in combination with
With the help of etoolbox's \preto each time \footnote is called it is checked wether it is used in the first or second column. If it is in the second column the footnote counter is reset if it hasn't been reset before. For this a new conditional is used that is set to true after the resetting and set to false again in the first column.
Although this worked nicely in my tests it might have drawbacks I'm not aware of.
\documentclass[twocolumn]{article}
\usepackage[perpage]{footmisc}
% or
% \usepackage{zref-perpage}
% \zmakeperpage{footnote}
% or
% \usepackage{perpage}
% \MakePerPage{footnote}
\usepackage{lipsum}% dummy text
\usepackage{etoolbox}
\makeatletter
\newif\iffootnoteresetted
\preto\footnote{%
\if@firstcolumn
\footnoteresettedfalse
\else
\iffootnoteresetted\else
\setcounter{\@mpfn}{0}%
\footnoteresettedtrue
\fi
\fi
}{}{}
\makeatother
\begin{document}
This is a test\footnote{Test}
This is a test\footnote{Test}
\lipsum[1-4]
This is a test\footnote{Test}
This is a test\footnote{Test}
\lipsum[1-4]
This is a test\footnote{Test}
This is a test\footnote{Test}
\newpage
This is a test\footnote{Test}
This is a test\footnote{Test}
\end{document}

multicolmight be a start. – Martin Schröder Nov 5 '12 at 14:57.auxfile and having to re-run ;) – tohecz Nov 13 '12 at 21:57