Non-administrators unable to tag contacts using Tags tab redux
I can't really see the use case where "Edit All Contacts" should be required for adding a tag.  I think this is something that should be changed.  So the solution is to submit a patch or ask a developer to do so.

Now, I'm not part of the CiviCRM core team - but I do submit patches like this one on behalf of my clients.  I'm pretty slammed, but I'll make you an offer.  If your organization is willing to join the CiviCRM Membership Program, I'll volunteer to fix this in an upcoming version of CiviCRM - and to help you install a personalized patch so you don't need to wait until you upgrade.

If this is amenable to you, please:


File an issue for this at https://issues.civicrm.org.  Reference this question, and mark the "Funding Source" as "Contributed Code".
Add a comment on this answer linking to your new issue.
In 1-2 days, the core team will reply.  If they agree that there's no legitimate case for "Edit All Contacts" permission to create tags, you'll join the membership program.  
I'll ask the membership coordinator to inform me when this happens.
At that point, I'll develop a patch, submit it to the core team, and work with you to get it working on your system.


Please let me know what you think!