gprof is the only profiler I have used on Linux. I don't know what alternatives there might be without searching for them.

For static analysis of a call tree, it's a very only time since I've had a need to do that. I don't recall the name of the tool I used. The current favourite seems to be Cscope which is installable from the Ubuntu repositories. I haven't tried it myself (or its interfaces such as the Vim interface).

At runtime, would have been great, but static is also manageable.
I don't understand the purpose. Static analysis tells you what can call what for all possible inputs, without following any particular path through the code. At runtime, you are after tracing the path through functions that are actually called for a given set of inputs. These give you significantly different information. I don't understand your underlying objective I'm afraid.