brett can be added at any point in the fermentation process and it will eat through some of the more difficult sugars left behind by your primary yeast (even at higher abv levels)... although in this case not likely all. what stage is your barley wine at now? in secondary? no need to rack another time, just dump cherries and brett right in. brett lambicus has been a pretty good performer for me, and with the additional sugar from the cherries, should take off pretty good in your barley wine.
I think brett lambicus is a good choice with the cherry puree. it will make the cherry aroma pop a bit more in my opinion.