Resposta específica do Linux:
perf-tools contém um execsnoop que faz exatamente isso. Ele usa vários recursos específicos do Linux, como o ftrace. No Debian, está no pacote perf-tools-unstable .
Exemplo de eu executando man cat
em outro terminal:
root@Zia:~# execsnoop
TIME PID PPID ARGS
17:24:26 14189 12878 man cat
17:24:26 14196 14189 tbl
17:24:26 14195 14189 preconv -e UTF-8
17:24:26 14199 14189 /bin/sh /usr/bin/nroff -mandoc -Tutf8
17:24:26 14200 14189 less
17:24:26 14201 14199 locale charmap
17:24:26 14202 14199 groff -mtty-char -Tutf8 -mandoc
17:24:26 14203 14202 troff -mtty-char -mandoc -Tutf8
17:24:26 14204 14202 grotty
Eu duvido que exista uma maneira portátil de fazer isso.