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:
