How does #value_callback really work (nested elements, ...)?
One thing i want to add before replying to your questions. Drupal core FAPI doesn't allow multiple #value_callback. It allow only one #value_callback per element type. Even You don't have to add #value_callback key in your hook_element_info() if your value callback follow the format form_type_' . $element['#type'] . '_value'.
// See code in include/form.inc from function _form_builder_handle_input_element line 2034

$value_callback = !empty($element['#value_callback']) ? $element['#value_callback'] : 'form_type_' . $element['#type'] . '_value';


            

1) How does #value_callback work, what should you return in it, etc. ?

value_callback provides a way to process values before they are returned to the form submit function. You need to provide a #value_callback if you want to do fancy processing on the input. If you just want #value set to #default_value, you don't need this hook at all, since that will happen anyway. This function is mainly useful if you need to do something non-standard with the value, like transpose an array into an option list.
Value callbacks should consider three conditions:


Input is being provided directly. This happens when a form is submitted.
No input is provided, but the field definition has a default value.
No input is provided and there is no default value.

1.1) what exactly are you supposed to return in #value_callback and why do the individual callbacks work in the way they do (or don't do in case of the first one).
So value callback is supposed to check the $input !== FALSE and then modify the $input value as per your logic. If its false that means $input value is not provided in this case you can return the $element['#defalut_value']. So in your first value callback TST_value_callback_1 if you want to make that work you have to return the value with the same array key something like.
function TST_value_callback_1($element, $input = FALSE, &amp;$form_state) {
  //example of input retrieving magic
  $input['testing_test'] = $input['testing_test'] . '_valc_';
  return $input;
}

In your second value callback TST_value_callback_2  it was adding value to $form_state['values']['inp'][0] because you was returning an array with index 0 having the value ABC_valc_ like array(0 =&gt; 'ABC_valc_');
// code from include/form.inc from function _form_builder_handle_input_element line 2109

// Set the element's value in $form_state['values'], but only, if its key
// does not exist yet (a #value_callback may have already populated it).
if (!drupal_array_nested_key_exists($form_state['values'], $element['#parents'])) {
  form_set_value($element, $element['#value'], $form_state);
}

1.2 is there any way how to make the #value_callback store the data in 'element root' ($form_state['values']['inp']), i.e. in the same place as if I used form_set_value in #element_validate?
Setting the #tree to false in your form element should do the trick.
$ar['inp'] = array(
  '#type' =&gt; 'TST',
  '#tree' =&gt; FALSE,
  );

you will be able to get the value in $form_state['values']['inp'] but in this case #value_callback will not do any affect, and $input in #value_callback is set to NULL  i don't know why. So you better use the ($form_state['values']['inp']['testing_test'])
2.1) Is there any way to enable 2.2 behavior without setting #value_callback in ?
2.2) Why are individual #value_callback functions run (and their outputs are saved to $form_state) only when parent (A) #value_callback is run (even if it doesn't reference or call the individual functions in any way)?
Hopefully my above explanation help you to understand the role of #value_callback. Even though custom element that is made of a nested set of other elements, are also elements so individual value callback will be called for each subelement. There is too much too explain Please take a look at _form_builder_handle_input_element
3) Do I understand this flowchart correctly that #value_callback is called before #element_validate?
yes #value_callback is called before the #element_validate callback. For more explanation See Creating Custom Elements
For practical example see examples module.
See also:
https://api.drupal.org/api/examples/form_example%21form_example_elements.inc/function/form_type_form_example_checkbox_value/7
https://api.drupal.org/api/examples/form_example%21form_example_elements.inc/function/form_example_phonenumber_combined_value/7