As an approximation, you could do:
trap '{ type -p -- "${BASH_COMMAND%% *}" >&3; } 3>&2 2> /dev/null' DEBUG
set -o functrace -o xtrace
The DEBUG trap is run before every command. During the execution of that trap, $BASH_COMMAND is set to the current command. That includes function calls, builtins, assignments... We call type -p on the first part of that up to the first space character with type's stdout retdirected to the shell's stderr (via fd 3, so that the xtrace output is redirected to /dev/null).
That's an approximation in that it won't work in cases like "cmd" foo or $CMD foo. Like for xtrace, beware of redirections of stderr.
Without modifying the script:
BASH_ENV=<(cat <<'EOF'
trap '{ type -p -- "${BASH_COMMAND%% *}" >&3; } 3>&2 2> /dev/null' DEBUG
EOF) bash -o functrace -x your-script
Or to have it in the PS4 prompt:
BASH_ENV=<(cat <<'EOF'
{ trap '{ cmdpath=$(type -p -- "${BASH_COMMAND%% *}")
} 2> /dev/null' DEBUG;} 2> /dev/null
EOF) PS4='+[$cmdpath] ' bash -o functrace -x your-script
or to avoid the fork:
BASH_ENV=<(cat <<'EOF'
{ trap '{ hash -- "${BASH_COMMAND%% *}";} 2> /dev/null' DEBUG;}2>/dev/null
EOF) PS4='+[${BASH_CMDS[${BASH_COMMAND%% *}]}] ' bash -o functrace -x your-script