By allowing free-form tagging you're opening the vocabulary up to the user's personal, local, cultural, and any other influence that comes along. The terms that the original poster uses to tag a photo may not be the ones that come to mind for the person doing the searching. That not only makes things hard to find, but also hard to exclude. In the case of your dog near the fire hydrant, then dog could also be an animal, a puppy, a pet, a spaniel, etc. A fire hydrant might be fire-hydrant or fire hydrent...
With free-form text, I don't think your example of scrolling to pick 'fire hydrant' in a list and then scrolling again to shift-click 'Portland, Maine' is very realistic. Lists are very fiddly things to use - they make it a laborious task to repeatedly scroll and find and re-find terms. They make it too easy to accidentally clear the selection, and you can't see all the selected terms at once. You may want to consider not having a list at all!
Your 'list of all tags' is going to get very long very quickly - and almost impossible to use as a list, leading to a much greater reliance on the autocomplete aspect of the input. You could mitigate this somewhat by allowing autocomplete suggestions to show a frequency of usage so that you guide the user toward effectively crowdsourced terms that are in 'popular' and demoting outlier terms that searchers will never think of using. Good examples are instagram or twitter hashtag suggestions. At no point do these platforms actually present a list of all the terms to scroll through!
There isn't just one instinctive correct way to express a term to be excluded. It's not even clear cut as to whether you might need to first express an intention to negate the next term you add, or whether you need to choose the term first and then mark it to be excluded. For example, if you know you want to negate the next term, you could type 'NOT' (or ! or something else) before adding 'dog', or first add the term 'dog' and then somehow negate it, which could be via a right click menu. Either way - things start getting a bit more complicated if you have to teach the user a language/notation or if the user has to thing about adding extra states to tags. Discoverability starts taking a dive in either case, and you shouldn't really have to teach the user how to do this sort of thing!
One way that is instinctive enough for anyone to use is to show two buckets up front - one field for for the terms to include and another one for the terms to exclude. The AND bucket would be where you enter all your terms as normal, so it's no more difficult for people to use who don't care about excluding terms. But if you do want to exclude some terms then there's a second input to add those terms.
Google or Twitter's advanced search has separate input fields for 'all of these words' and 'none of these words'. They also have many other options which is why it's 'advanced'. You could hide the excluded item feature behind an 'advanced search' button, but if that's the only additional feature, maybe it's not necessary.
You may find in the future that you do want to get a bit more advanced. For example - I might want fire hydrants in Portland or Bangor - i.e. logically 'A AND (B OR C)'. It's not long before things get messy there too, but again, typical advanced searches just add another bucket like 'any of these', to go with the 'all of these' and 'none of these' buckets. The 'two bucket' route is an extensible way of doing things.