gdb

How can we list all the functions being called in an application

For any realistically sized application, this list will have thousands of entries, which will probably make it useless.

You can find out all functions defined (but not necessarily called) in an application with the nm command, e.g.

nm /path/to/a.out | egrep ' [TW] '
EG：
[root@monitor ~]# nm ./test | egrep ' [TW] '              
00000000004005f0 T __libc_csu_fini
0000000000400600 T __libc_csu_init
00000000004006c8 T _fini
00000000004003c8 T _init
0000000000400420 T _start
0000000000600990 W data_start
0000000000400504 T main

You can also use GDB to set a breakpoint on each function:

(gdb) set logging on     # collect trace in gdb.txt
(gdb) set confirm off    # you wouldn't want to confirm every one of them
(gdb) rbreak .           # set a breakpoint on each function
 Once you continue, you'll hit a breakpoint for each function called.
 Use the disable and continue commands to move forward. I don't believe there is an easy way to automate that, unless you want to use Python scripting.

Already mentioned gprof is another good option.

record function-call-history should be a great hardware accelerated possibility 

if you are one of the few people (2015) with a CPU that supports Intel Processor Tracing (Intel PT, intel_pt in /proc/cpuinfo).

GDB docs claim that it can produce output like:

(gdb) list 1, 10
1   void foo (void)
2   {
3   }
4
5   void bar (void)
6   {
7     ...
8     foo ();
9     ...
10  }
(gdb) record function-call-history /ilc
1  bar     inst 1,4     at foo.c:6,8
2    foo   inst 5,10    at foo.c:2,3
3  bar     inst 11,13   at foo.c:9,10
Before using it you need to run:

start
record btrace
which is where a non capable CPU fails with:

Target does not support branch tracing.
CPU support is further discussed at: How to run record instruction-history and function-call-history in GDB?