IDK how it is possible but WPF Inspector is exactly able to do what I was looking for (now I need to know how they attach to the WPF application :) ).
____OLD ANSWER____ It seems impossible to change the XAML of other programs. If the developers are "too lazy" to set the AutomationId, I've come up with a alternative solution.
The automation app iterates over all controls in the beginning, giving them unique names which are stored in a dictionary, together with their references. In case a component gets added/deleted/changed in the hierarchy, the component and their descendants get deleted in the dictionary and the app re-iterates over this sub-tree again.