Computer Cipher

Perl 6, 125 bytes

->\n{*.&{S:g{.}=(65..90)>>.chr.roll(n).join.subst(/./,$/,:th($!=roll 1..n:)).subst(/./,$!,:th($!-1??(^n+1∖$!).roll!!n+1))}}

Try it online!

Takes input and output in uppercase. Takes input curried, like f(n)(string). Uses 1 indexing.

Explanation:

->\n{*.&{ ...  }}   # Anonymous code block that takes a number n and returns a function
     S:g{.}=        # That turns each character of the given string into
                          .roll(n)      # Randomly pick n times with replacement
            (65..90)>>.chr              # From the uppercase alphabet
                                  .join # And join
            .subst(                         ) # Then replace
                   /./,  ,:th($!=roll 1..n:)  # A random index (saving the number in $!)
                       $/               # With the original character
            .subst(                )    # Replace again
                   /./,$!,:th( ... )    # The xth character with $!, where x is:
                           $!-1??          # If $! is not 1
                                 (^n+1∖$!).roll       # A random index that isn't $!
                                               !!n+1  # Else an index out of range

Python 2, 187 177 176 156 154 148 bytes

lambda l,s:''.join([chr(choice(R(65,91))),c,`n`][(j==n)-(j==i)*(n>0)]for c in s for n,i in[sample(R(l),2)]for j in R(l))
from random import*
R=range

Try it online!

Uses uppercase letters, and 0-indexed numbers.

_{-3 bytes, thanks to Kevin Cruijssen}

JavaScript (Node.js), 135 bytes

n=>f=([c,...s])=>c?(g=n=>n?g(--n)+(n-p?n-q|!p?(r(26)+10).toString(36):p:c):'')(n,r=n=>Math.random()*n|0,p=r(n),q=r(n-1),q+=q>=p)+f(s):s

Try it online!

Thank Arnauld for 1B