The new python bindings to the MemoryDatasource should make it a bit easier to write python class to render a legend since it is now possible to create special-crafted features to feed each symbolizer so that it renders it at a specific location of the pixmap.
See wiki:Legending for the spec.
I assign to myself since I hope to spare some time to give it a shot in the next couple of days. However, feel free to re-assign if there's no progress in two weeks.
[springmeyer] check out the work happening over at https://github.com/thjc/mapnik-svg
Full link to wiki page: https://github.com/mapnik/mapnik/wiki/Legending
best done outside mapnik, but see also https://github.com/mapnik/mapnik/blob/master/bindings/python/mapnik/printing.py