What hook can access every field label at once and change the label of one?
A guaranteed solution for all fields is hard. It depends on:


The field formatters you have chosen 
the template files used


For a general approach try:

/**
 * Implements hook_preprocess_HOOK().
 */
function YOUR_MODULE_preprocess_field(&amp;$variables) {
  if ($variables['element']['#field_name'] == 'YOUR_DEPENDENT_FIELD' &amp;&amp; !empty($variables['element']['#object']-&gt;YOUR_DEPENDENCY_FIELD)) {
    // YOUR LOGIC IN RELATION TO YOUR_DEPENDENCY_FIELD
    $new_value = 'something';
    $variables['label'] = $new_value;
  }
}


Notes: 


This will change the label display everywhere, not only on a
node display. Since you don't mention anything about view modes, I
guess the given solution is good enough.
Make sure you sanitize $new_value if you are showing user input.