Jelly, 22 20 bytes

ẹ@ße?";@FƑƇQɗƤ
çWịØa

Try it online!

Input and output as ragged lists of Jelly strings; the test footer converts from and to the string format for convenience.

ẹ@ße?";@FƑƇQɗƤ    Dyadic helper furlong: recursively assign indices
                                         to identifiers from the left
                                         with the parent scope on the right

     "            For each element from the left argument
           Q      and the unique
        FƑƇ       identifiers at the top level of
     "      ɗƤ    its corresponding prefix of the left argument
      ;@          appended to the right argument,
     ";@FƑƇQɗƤ    i.e. with an expression on the left and scope on the right,
  ße?             recur if the expression is not in the scope (is a block),
ẹ@                else get the (singleton) list of its indices in the scope.

çWịØa    Main furlong

ç        Call the helper with the input on the left
 W       and a singleton list containing the input on the right,
  ị      then index every integer in the resulting ragged list into
   Øa    the lowercase alphabet.

Note carefully that, although Jelly types are thinly and naively implemented as Python types, Jelly has distinct character and string types--a Jelly character is a length-1 Python string, while a Jelly string is a list of characters. ẹ is used over i because indexing a scalar into a string such as Øa produces a single character, rather than a string, which would then violate the requirement that a solution's output must be in a format it accepts as input.

Also, the wrapped input is used for the initial scope instead of an empty list simply as a 1-byte save compared to the empty list “”, because it is immediately filtered out.

Rust, 277 276 bytes

• -1 byte thanks to CeilingCat

enum N{A(String),B(Vec<N>)};fn f(a:&[N],b:&mut Vec<String>)->Vec<N>{a.iter().map(|j|match j{N::A(j)=>N::A(('a'..'{').map(|i|i.to_string()).nth(b.iter().position(|a|a==j).unwrap_or_else(||{b.push(j.clone());b.len()-1})).unwrap()),N::B(j)=>N::B(f(j,&mut b.clone()))}).collect()}

Playground Link

Perl, 63 60 29 bytes

(+1 for -p)

s/\w+/$a{$&}||=chr$i+++97/ge

Run like:

$ perl -pe 's/\w+/$a{$&}||=chr$i+++97/ge' <<<"(rudolf)"

or even

$ perl -pe 's/\w+/$a{$&}||=chr$i+++97/ge' file

Ungolfed and explained

This is a simple replacement using the powerful /e modifier, which instructs perl to evaluate the replacement as code. It finds each identifier and checks it against a hash. If the hash is empty, it populates the next available letter, starting with ASCII code 97 (a):

s/                     # substitute
   (\w+)               # match: 1+ word characters
 /
   $letter{$1} ||=     # use existing letter or else assign …
      chr($i++ + 97)   # … a char w/ value of $i + 97, then increment $i
 /gex;                 # match globally and eval the replacement as code
                       # (this explanation uses /x for comments & spacing)

Running through the examples on a file containing each test case on its own line:

$ while IFS= read line; do 
    printf "%-30s  %s\n" "$line" \
      "$(perl -pe 's/\w+/$a{$&}||=chr$i+++97/eg' <<<"$line")"
  done < test-cases
(rudolf)                        (a)
(mousetail mousetail)           (a a)
(cart fish)                     (a b)
(no and no)                     (a b a)
(burger (and fries))            (a (b c))
(burger (or burger))            (a (b a))
(let (bob and) (bob let))       (a (b c) (b a))
(let (a (fish (let))))          (a (b (c (a))))
(kor (kor kor) (kor kor))       (a (a a) (a a))
((kor) kor)                     ((a) a)
(aa (ab ac ad) (ad ad) ad)      (a (b c d) (d d) d)
(aa not (ab ac ad) (ad ad))     (a b (c d e) (e e))
(((((do) re) mi) fa) so)        (((((a) b) c) d) e)
(do (re (mi (fa (so)))))        (a (b (c (d (e)))))
((mark sam) sam)                ((a b) b)

This prints the input in a 30-char column before printing the answer.

Prolog (SWI), 81 70 bytes

\X,[I]-->[H],{copy_term(X,Z),\(Z,H,I);nth1(I,X,H)},(\X;[]).
a--> \_,!.

Try it online!

Instead of using predicates, I use definite clause grammar (DCG) notation. DCG notation is syntactic sugar in Prolog that allows for more writing more concise code for sequence processing. The basic way my program operates is that it iterates through the input and output list using DCG notation to bind the first item of the remainder of the input list to NextItem and the first item of the remainder of the output list to ProcessedItem. Then the program handles each potential case for NextItem and binds ProcessedItem to the appropriate value. Finally, the program attempts to process the following items, or, if none are found, terminates.

I stumbled onto an 11 byte golf of my program when I realized my original code was broken. The issue was that when parsing a sublist, the inner scope would leak into the outer scope since InScopeVars was having new variables placed into it by nth1/3, instead of by the intended append/3. I found a way to exploit this behavior though with the copy_term/2 predicate, which unifies the second argument with a copy of the first argument but with fresh variables (e.g. copy_term(X,Z) where X=[aa|SomeVar] unifies Z with [aa|SomeNewVar]). This allows us to create a copy of the scope to use when handling a sublist where its uninitialized tail can be used without the inner scope leaking, thereby allowing us to use nth1/3 for both appending and finding the index.

Ungolfed Code

rename_item(InScopeVars),
  [ProcessedItem]
  -->
    [NextItem],
    {
      % Case 1: NextItem is a sublist
      % This predicate sets InScopeVarsCopy to a copy of InScopeVars,
      % but replaces all Prolog variables in it with newly instantiated ones.
      % This means any unifications that occur in the following rename_item call
      % will not affect InScopeVars
      copy_term(InScopeVars, InScopeVarsCopy),
      % DCGs are syntactic sugar for predicates with an additional two arguments:
      % the input sequence and the output sequence.
      % This fails if NextItem is not a list, in which case we'll
      % do Case 2 instead.
      rename_item(InScopeVarsCopy, NextItem, ProcessedItem)
    ;
      % Case 2: NextItem is a variable
      % We unify ProcessedItem with the index of NextItem in the list InScopeVars.
      % Note that since InScopeVars initially uninitialized,
      % it gets unified with [NextItem|UninitializedVariable].
      % On later calls, if NextItem appears in InScopeVars then ProcessedItem is
      % unified with the index of NextItem.
      % Otherwise the head of the uninitialized tail of InScopeVars is set to
      % NextItem, and NextItem's new index in InScopeVars is unified with
      % ProcessedItem.
      nth1(ProcessedItem, InScopeVars, NextItem)
    },
    (
      % Attempt to rename the next remaining item in the list
      rename_item(InScopeVars)
    ;
      % If that fails then we are done!
      []
    ).

rename -->
  % Due to the way the nth1/3 predicate works, passing in an
  % uninitialized variable for the initial scope is in essence passing in an
  % infinite list of uninitialized variables.
  % As we encounter new (not Prolog) variables in the input program they will be
  % unified with the first uninitialized (Prolog) variable in the scope.
  rename_item(_),
  % Once we get the first solution, we use the cut to prevent backtracking
  !.

Before I realized that it was permitted to output numbers instead of letters I wrote the following program, which I've modified to use some of the golfs I later found:

92 bytes

\X,[I]-->[H],{copy_term(X,Z),\(Z,H,I);nth1(N,X,H),C is 96+N,name(I,[C])},(\X;[]).
a--> \_,!.

Try it online!

Prolog (SWI), 101 bytes

This version uses 1-26 instead of a-z (alternative version for a-z below). Had to (re)learn about Prolog dictionaries for this one, I like them!

[H|T]+[I|U]+A/N:-(H@>[],H+I+A/N;I=A.get(H)),T+U+A/N;I is N+1,T+U+A.put(H,I)/I.
A+A+_.
A+B:-A+B+_{}/0.

Try it online!

(The H@>[] part is a bit hacky, it's a list check (is_list(H)) that works on TIO, but there's probably a way to get rid of it, as neither are necessary in my ungolfed solution. Please correct me!)

Ungolfed, commented

f([H|T],[NewH|NewT],Dict,N):-
% Case 1) No dict update needed
  ( f(H,NewH,Dict,N); % First element is a list (matches f([H|T]... or f([]...)
    NewH=Dict.get(H)), % First element is an atom
  f(T,NewT,Dict,N);
% Case 2) If first part failed, need to update the dictionary
  NewH is N+1,
  NewDict = Dict.put(H,NewH),
  f(T,NewT,NewDict,NewH).
f([],[],_,_).

% Wrapper predicate for recursive predicate
A+B:-f(A,B,_{},0).

a-z solution, 114 bytes

[H|T]+[I|U]+A/N:-(H@>[],H+I+A/N;I=A.get(H)),T+U+A/N;Z is N+1,name(I,[Z]),T+U+A.put(H,I)/Z.
A+A+_.
A+B:-A+B+_{}/96.

Try it online!

JavaScript (Node.js), 109 bytes

s=>s.replace(/\w+|\S/g,m=>m>')'?v[m]=v[m]||Buffer([v[0]++]):(v=m<')'?S.push(v)&&{...v}:S.pop(),m),S=[v=[97]])

Attempt This Online!

Ungolfed and Explained

str => str.replace(
  /\w+|\S/g,                          // replace each variable name or bracket
  m => m > ')' ?                      // if match is a variable
    v[m] = v[m] || Buffer([v[0]++]) : // lookup the new var name, otherwise assign new
    (
      v = m < ')' ?                   // otherwise, if match is opening bracket
        S.push(v) && {...v} :         // push current var dict to stack
        S.pop(),                      // otherwise pop var dict
      m                               // return matched bracket (no-op)
    ),
  S = [                               // initialise stack
    v = [                             // initialise var dict
      97                              // v[0] = char code of next var name
    ]
  ]
)

K (ngn/k), 65 54 bytes

{$[x~*x;`s$`c$97+(s::?s,x)?x;[t:s;r:o'x;s::t;r]]};s:!0

Try it online!

C (clang), 208 bytes

a[26];b[26];c;d;e;f;g;h;i(*j){for(;f=*j;j++)if(f/47)c=c?:j;else{if(c){for(*j=g=d=0;a[d]*!g;wcscmp(a[d],c)?d++:g++);g||(a[d]=c,b[e=d]=h);putchar(d+97);}for(c=!putchar(f);f==41&b[e]==h;a[e--]=0);h+=f%17-47%f;}}

Try it online!

-1 byte thanks to Noodle9!

-2 bytes thanks to ceilingcat!

-1 byte thanks to c--!

tinylisp, 149 bytes

(load library
(d G(q((L N)(i(c()(h L))(i L(c(G(h L)N)(G(t L)N))L)(i(contains? N(h L))(c(last-index N(h L))(G(t L)N))(G L(insert-end(h L)N
(q((L)(G L(

The last line is an anonymous function that takes a nested list and returns a nested list. The returned list uses nonnegative integers instead of letters, which seems to be allowed by this comment.

Try it online! Or, verify all test cases.

Ungolfed

(load library)

(def _rename
 (lambda (expr names)
  (if (type? (head expr) List)
   (if expr
    (cons
     (_rename (head expr) names)
     (_rename (tail expr) names))
    nil)
   (if (contains? names (head expr))
    (cons
     (last-index names (head expr))
     (_rename (tail expr) names))
    (_rename expr
     (insert-end (head expr) names))))))

(lambda (expr) (_rename expr nil))

Here's a 167-byte version that uses letters instead of numbers:

(load library
(d G(q((L N)(i(c()(h L))(i L(c(G(h L)N)(G(t L)N))L)(i(contains? N(h L))(c(single-char(a(last-index N(h L))97))(G(t L)N))(G L(insert-end(h L)N
(q((L)(G L(

Try it online!

Ruby, 69 65 60 bytes

f=->l,*r{l.map{|x|x*0==[]?f[x,*r]:""<<97+(r|=[x]).index(x)}}

Try it online!

Raku, 76 bytes

sub f($x,%h?){$x~~Str??(%h{$x}//=chr 97+%h)!!$x.map:{f $^a,$_}with %h.clone}

Try it online!

Python, 79 bytes

f=lambda _,**s:[i==[*i]and f(i,**s)or s.setdefault(i,chr(97+len(s)))for i in _]

Attempt This Online!

Thanks to @loopy walt.

Whython, 66 bytes

f=lambda _,**s:[s.setdefault(i,chr(97+len(s)))?f(i,**s)for i in _]

Attempt This Online!

Port of the above.

Whython, 72 bytes

f=lambda a,s={}:s.setdefault(a,chr(97+len(S:={**s})))?[f(i,S)for i in a]

Attempt This Online!

My original solution