Bulk Action
Lets look at the option that you like and review the pros and cons.
A button activates a bulk "mode"
Pro:
- Being in a select mode keeps the user in a focus mode.
- You don't have to overload with user with actions that he does not need to use before selecting items.
Cons:
- Visibility: Users don't naturally know that there is mode that would allow them to select item. Visibility of information translates directly to better decision making.
- Iconography: You are asking the user to guess the icon you think fits.
Visibility is the basic principle that the more visible an element is, the more likely users will know about them and how to use them. Equally important is the opposite: when something is out of sight, it's difficult to know about and use.
The above statement seems true in this case. There is enough real estate on the screen to accommodate all the UI that will help/encourage the user to make their decisions.
I like the feeling of being "in" a mode (option 2), but am struggling to articulate why I prefer this. The ESC key would exit you out of the mode.
I think hiding this action from the user to begin with make it harder to argue for the design. What could be a valid reason to now show check boxes when you have real estate.
I also like the control that including a "deselect" link gives, but worry it's over-engineered.
I don't think it's over-engineered. I think it is necessary in order to give the user the option to correct the mistake. However, reconsider the word Deselect.
Keeping items selected vs deselecting after actions. I can see pros and cons for both options.
Why would you keep items selected? The user has already performed the action. Take them back after providing feedback if the action went through or not.
Based on your designs, here is a solution.
Visibility of system: Show Check box and actions

System Feedback: System is able to tell user what happened and how they can go back

Return to zero state: Provide feedback on action and return to zero state

Few things to improve:
- Provide a header to differentiate list values
- You don't need a single action item. make the title clickable
- Provide a dropdown to add tags to individual rows. Show dropdown on hover(maybe)

Actions
I think what I see in your action drop down is enough. It's dificult to understand what you mean by "intermediate" state.
As long as you provide a way to add, remove and show the added state before applying changes. you're good.