What are the differences between using profilers that need to recompile the source code with debugging options(like gprof) and profilers that do not need recompiling(like Valgrind, OProfile, ...)?
I'm not familiar with the named profilers but there are two major approaches to profiling:
Instrumentation, this method usually requires recompiling (not always, for example java and .Net applications can be instrumented dynamically). With this method it is possible to measure exactly how often a routine is called, or how many iterations a certain loop makes.
Sampeling is a method that does not require any recompiling, it simply takes a snapshot of the stack with set intervals. This has proven to be an effective way to find bottlenecks.
There is some more info about the two strategies here