VBO comes, out of the box, with some predefined (hardcoded) operations that can be applied to each row selected in the view. The available operations are shown within "Selected bulk operations" when configuring the VBO field. Obviously, something like Edit taxonomy terms isn't one of them.
However using Rules (Conditions and/or Actions) you can execute a VBO operation which you define using a Rules Component. To get the idea, have a look at the video about Using Rules components with VBO" uses a Rules Component with (only) 1 parameter. If you want even more, then also watch the subsequent "Using Rules components with more than one parameter" video. This video actually shows how to (also) add a term to a node, so it should be pretty forward to use a similar technique.
For an example in which this technique is used, refer to the answer to "How to implement the mass operations on the Group's members page using Views?".
Note: to process thousands of nodes at once is quite a challenge (memory requirements, etc). Therefor you might want to also watch the video about "More details about VBO settings" ... Before you are tempted to use VBO for processing them all at once ...
Happy VBO-ing while Rules-ing!