Vyxal, 1413 bytes

:ẏÞS℅~İṖ℅Z(n÷Ȧ

Try it Online!Try it Online!

Explained

:ẏÞS℅~İṖ℅Z(n÷Ȧ
:ẏ             # Push the input and the range [0, len(input))
  ÞS℅          # Choose a random sublist of indices
     ~İ        # And index into the input at those places, without popping anything
       Ṗ℅      # Choose a random permutation of the indexed items
         Z     # and zip that with the chosen indices - this creates a list of [[original index, new item]...]
          (    # for each pair:
           n÷Ȧ # input[original index] = new item