h
#copy input string 'A' to hold space
:
#start loop
    s:.*:shuf -i32-126|dc -e?P:e
    #run shell command to replace pattern space with a random printable ASCII char

This works by using shuf to output a random permutation of the input lines consisting in this case of the numbers from 32 to 126. I use dc ? command to read only the first line, and P to convert the read decimal to an ASCII char.

    H;g
     #append char to hold space (ex: 'A\n.'), copy result back to pattern space
    s:\n::2g
     #remove all newlines from pattern space, but first (not needed for 1st iter)
    /^(.+)\n(.*)\1/{
     #if pattern is 'A\nB', with B as '.*A' (A is a substring of B), then
        s::\2\1:;q
         #search previous regex used, line above, leave only string B, then quit
        #implicit printing before exiting
    }
b
#repeat loop

• input length: 1, 10 random inputs (runs), average time: < 1 s
• input length: 2, 10 random inputs (runs), average time: 90 s
• input length: 3, 10 random inputs (runs), average time: (coming soon)

h                                # copy input string 'A' to hold space
:                                # start loop
    s:.*:shuf -i32-126|dc -e?P:e # run shell script: shuf outputs a rnd permutation
                                 #of the set of numbers from 32 to 126, and '?P' in
                                 #dc converts the 1st read decimal to an ASCII char
    H;g                          # append char to hold space ('A\n.'), then copy 
                                 #result back to pattern space
    s:\n::2g                     # remove all '\n's from pattern space, but first
    /^(.+)\n(.*)\1/{             # if pattern is 'A\n.*A' (A substring of B), then
        s::\2\1:;q               # search previous regex used and leave only '.*A', 
                                 #then quit (implicit printing before exit)
    }
b                                # repeat loop

• input length: 1, 10 random inputs (runs), average time: < 1 s
• input length: 2, 10 random inputs (runs), average time: 90 s
• input length: 3, 10 random inputs (runs), average time: lots of hours!

GNU sed + coreutils, 75 + 1(r flag) = 76 bytes

h
:
s:.*:shuf -i32-126|dc -e?P:e
H;g
s:\n::2g
/^(.+)\n(.*)\1/{s::\2\1:;q}
b

Try it online! (It takes a lot of runs to get an answer for a length 2 input, because most of the time you run out of allowed TIO computation time.)

Explanation coming soon.

GNU sed + coreutils, 75 + 1(r flag) = 76 bytes

h
:
s:.*:shuf -i32-126|dc -e?P:e
H;g
s:\n::2g
/^(.+)\n(.*)\1/{s::\2\1:;q}
b

Try it online! (It takes a lot of runs to get an answer for a length 2 input, because most of the time you run out of allowed TIO computation time.)

Explanation:

h
#copy input string 'A' to hold space
:
#start loop
    s:.*:shuf -i32-126|dc -e?P:e
    #run shell command to replace pattern space with a random printable ASCII char

This works by using shuf to output a random permutation of the input lines consisting in this case of the numbers from 32 to 126. I use dc ? command to read only the first line, and P to convert the read decimal to an ASCII char.

    H;g
    #append char to hold space (ex: 'A\n.'), copy result back to pattern space
    s:\n::2g
    #remove all newlines from pattern space, but first (not needed for 1st iter)
    /^(.+)\n(.*)\1/{
    #if pattern is 'A\nB', with B as '.*A' (A is a substring of B), then
        s::\2\1:;q
        #search previous regex used, line above, leave only string B, then quit
        #implicit printing before exiting
    }
b
#repeat loop

Benchmark: approximate, for scaling purposes only

• input length: 1, 10 random inputs (runs), average time: < 1 s
• input length: 2, 10 random inputs (runs), average time: 90 s
• input length: 3, 10 random inputs (runs), average time: (coming soon)