With zsh instead of bash:

() {print -rC1 -- $tdir/$^@} $fdir/*.mp3(Noe['REPLY=$RANDOM']:t)

Or assuming neither $fdir nor $tdir contain : characters:

print -rC1 -- $fdir/*.mp3(Noe['REPLY=$RANDOM']:s:$fdir:$tdir)

With zsh instead of bash:

() {print -rC1 -- $tdir/$^@} $fdir/*.mp3(Noe['REPLY=$RANDOM']:t)

Or assuming neither $fdir nor $tdir contain : characters:

print -rC1 -- $fdir/*.mp3(Noe['REPLY=$RANDOM']:s:$fdir:$tdir)

With bash 4.4+ and GNU shuf (or sort -zR), you can always do:

print0()  { [ "$#" -eq 0 ] || printf '%s\0' "$@"; }
println() { [ "$#" -eq 0 ] || printf '%s\n' "$@"; }

readarray -td '' listing < <(
  shopt -s nullglob
  cd -P -- "$fdir" && print0 *.mp3 | shuf -z)
println "${listing[@]/#/$tdir}"

Or:

print0()  { [ "$#" -eq 0 ] || printf '%s\0' "$@"; }
println() { [ "$#" -eq 0 ] || printf '%s\n' "$@"; }

readarray -td '' listing < <(
  shopt -s nullglob
  print0 "$fdir"/*.mp3 | shuf -z)
println "${listing[@]/#"$fdir"/$tdir}"

as an equivalent.