Pgfplots has a couple of helper methods which do the job - and these methods are mostly independent of any axis. The only required things are the text labels and the styles for the individual images.
Here is a short draft which might do what you want:
% argument #1: any options
% inits/clears the lists (which might be populated from previous
% draws the legend:
% makes \addlegendimage available (typically only available within an
% axis environment):
\addlegendimage styles are a little bit ... inconsistent, but I wanted to experiment if they work. I guess that
mesh legend might produce problems, so stick to the simpler ones...