What can you do if someone gets this out?? {Avacyn, Angel of Hope}
{Oblivion Ring} or morbid {Tragic Slip}
Make them sacrifice their stuff with {Killing Wave}
{Merciless Eviction}, {Terminus}
{swords to plowshares}, {clone}, {slave of bolas}, {condemn}, {pacifism}, {dispatch}, lots of stuff can deal with avacyn...
{All is Dust}!
You cast your own {Avacyn, Angel of Hope}
Wait would the legends thing work? Since avacyn an all permanents you control are indestructible
Legend rule isn't a "destroy" effect, so yes, it would work.
{Clone}
{Phyrexian Metamorph}
KILL IT!!! KILL IT WITH FIRE!!!!
Steal it
What if I am working with a standard green black deck myself??
The previously mentioned {Killing Wave} and {Tragic Slip}, plus {Devour Flesh}, {Liliana of the Veil}, and {Mutilate} or {Liliana of the Dark Realms}'s -3 if you have enough swamps. I can't think of anything green can do about her.
Also {Death's Approach} or {Death Wind} or {Barter in Blood}
{Helvault} could be used as well
Definitely use {helvault} if nothing else than the delicious flavor of removing her with her own prison
Grab the card and begin eating it. When you are done, proclaim that there is no longer a threat on the field. XD
Or besides of all the good suggestions above you can always wait until October and WotC will solve ur problem for you... If it bothers you in standard...:D
Edit: I know, that's not a really constructive help...;)