How to flag term reference without flagging term?
You may use the Relation module. 

Relation allows you the create relations between entities that are entitties too. So the scheme will be:


Create a relation between your users and the skills entities (they can still be taxonomy terms).
Because these relation instances between your users and the skills are entities you can create a flag for this relation entities. So, when a user adds a skill to the profile you will have to create one relation entity with the user (or profile2*) and the skill.
When anotheruser wants to aprove this user's skill she will flag that entity relation. No other user is affected. 


I checked Relation time ago and I remember that creating relations was a little bit tricky. I don't remember how to make relations so I can't help you in this point, sorry. You may need some custom code to achieve what you want.

*: to decide between Profile 2 or user take into account how are you going to show this information. For example, think which options fits better with Views.