I'm deeply convinced that graphviz should not be used this way, but you may use HTML labels to achieve what you want:
digraph  { 
Foo -> Bar -> Test;
Foo -> Baz -> Test;
{ rank = sink;
    Legend [shape=none, margin=0, label=<
    <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
     <TR>
      <TD COLSPAN="2"><B>Legend</B></TD>
     </TR>
     <TR>
      <TD>Foo</TD>
      <TD><FONT COLOR="red">Foo</FONT></TD>
     </TR>
     <TR>
      <TD>Bar</TD>
      <TD BGCOLOR="RED"></TD>
     </TR>
     <TR>
      <TD>Baz</TD>
      <TD BGCOLOR="BLUE"></TD>
     </TR>
     <TR>
      <TD>Test</TD>
      <TD><IMG src="so.png" SCALE="False" /></TD>
     </TR>
     <TR>
      <TD>Test</TD>
      <TD CELLPADDING="4">
       <TABLE BORDER="1" CELLBORDER="0" CELLSPACING="0" CELLPADDING="0">
        <TR>
         <TD BGCOLOR="Yellow"></TD>
        </TR>
       </TABLE>
      </TD>
     </TR>
    </TABLE>
   >];
  }
} 
That's what this looks like:

The positioning of the Legend has to be done like any other node (I used rank=sink to get it to the bottom) - you may play with its margin attribute for fine-tuning the position.
Edit:
Without using labels, that may be the direction to go for - I'm not sure whether it is to completely eliminate ranksep.
digraph  { 
 mindist=0;
 ranksep=0;
 nodesep=0;
 node[shape=box,margin="0,0",width=1, height=0.5];
 edge [style=invis];
 Legend[width=2];
 Legend -> Foo;
 Legend -> FooValue;
 Foo -> Bar;
 FooValue -> BarValue
 Bar -> Baz;
 BarValue -> BazValue;
 edge [constraint=false];
 Foo -> FooValue;
 Bar -> BarValue
 Baz -> BazValue;
 }
Resulting in:
