Actually, you can pull up all users (or any entity) based on a field value by using the 'Fetch entity by property' action.
Since users (and nodes, and comments, etc) are all entities, you can use this action to pull up a list of users with a certain value in a field.
In your rule, that gets fired upon the update of a node, simply
- add the 'Fetch entity by property' action,
- select 'User' as the entity type, and
- in the final screen choose the field (in your case a term reference) you want to check and the specific value you're checking for.
- Feel free to change the name of the entities it will fetch for you. By default they will be called fetched_entity.
THEN, add a loop to your action set after this fetch, to go through each of the found entities. In this loop, we'll check for your second field and exclude the necessary ones. From what I understand, you'll want to exclude the ones whose uid matches the user reference field on the edited node.
So here's how:
By now your rule's action set should look like this: You're fetching users by your taxonomy property, then you'll looping through all the found entries (make sure it's pulling as many as you want, because it limits to 10 by default, by the way).

Now, add a component in your rules. Components are used when you need an entirely new rule to execute in your action area. Now that we're looping through users, we need an entirely new rule to call (IF the user doesn't have field x, THEN do y). However, when we're in the action area, we can't call conditions. So that's why we'll create a component that's a rule within itself, and call it from here.
- Go to admin/config/workflow/rules/components or Configuration --> Workflow --> Rules --> Components
- Click to "Add new component"
- Select "Rule" for the component plug in. We don't want it to be just a condition test or an action, we want it to contain both a condition and action!
- Call it something like "Email non-referenced users" or something like that
- We will pass it two parameters. We need to pass it the user we're currently looping through and the node that has just been changed (that triggered the rule) because we'll compare the user's uid with the node's user reference field.

- Add a condition to your component that is a 'Data comparison' condition and compare the looped_user:uid (or whatever you called that incoming parameter) to the user reference field of your updated_node (or whatever you called that incoming parameter)
- Careful here, make sure to check the 'Negate' checkbox at the bottom of that condition. We want to let through only those users for whom the two fields DON'T match, i.e. the ones that aren't referenced.
- As an action in the component, have the system send out the email you want
Voila! Almost done. This component now narrows down our looped users (with the correct terms) to those who aren't referenced and emails them. The one thing we have left to do is to CALL this component in our user loop.
Go back to your original rule, and click 'Add action' to your loop (not below it, but on it)

In your list of actions, at the very, very bottom, you will see the names of components you have created. Your new component should be there. Just select it, and pass it the updated node and the 'fetched_entity' (which is your currently looped users) as the two parameters.
Test!
Hope this helps.