Permission to add contact data, not edit existing
One way of accomplishing this more refined permission stuff involves thinking outside of the civi box and using Drupal Webforms (and perhaps Views)
Eg, build a Views based search, such that the results load up a webform with the cid in the url, this loads that contact on to the webform at which point you have total control over which fields are editable and which are only viewable.