The dynamic legend features were added at 10.1. The only way that I can think to do it at 10.0 would be to build a legend with all possible symbols and text, then break the legend up into individual parts and use arcpy.mapping to automate the building of the legend. Parts not needed would stay off the page and the those in the data view (identified based on queries) would be placed using x/y placement logic.
Jeff