So, is there any tool to log/record Http Request/Responses and what call graph of the php app it triggered? Preferably something that would not have to get written into the code?
The code coverage analysis functionality of xdebug will help you get a sense of what gets executed on each request:
Code coverage tells you which lines of script (or set of scripts) have been executed during a request. With this information you can for example find out how good your unit tests are.
xdebug's profiler outputs profiling information in the form of a Cachegrind compatible file, so in theory you don't have to do a lot in code, as you can configure xdebug via php.ini and htaccess.
This is the practical approach, don't stop here, you should follow the advice given by ChrisFChrisF and MoronsMorons.