LiveScript, using Bruijin Indices: <s>144</s> <s>135</s> 133

    s=(I=id;(c=(a,b=I,f=I,l=1)->map ((x)->x.toFixed&&(g=x==l&&b||x>l&&f||I;g x,l)||c x,b,f,l+1),a);(a,b)->c a,((x,l)->c b,I,(->it+l)),I)

**Edit:** below is a more complete version which fills the requirements of the thread, I guess. It has lots of rooms for improvement, though, as I have 2 very similar functions. I am using arrays in the form `[f x]` to denote application, objects in the form `{λ:body}` to denote abstractions and integers to denote bruijin indices.

**280 characters**

    λ=(.λ?);P=(.forEach?);N=(.toFixed?)
    S=(t,b=I,f=I,l=0)->|N t=>f t;|λ t=>λ:S t.λ,b,f,l+1;|P t=>R map ((x)->(N x)&&(g=x==l&&b||x>l&&f||I;g x,l)||S x,b,f,l),t
    A=(a,b)->|N a=>[a,b];|λ a=>(S a,((x,l)->S b,I,(->it+l-1)),(--)).λ|P a=>[(A a.0, a.1),b]
    R=(a)->(P a)&&(A (R a.0),(R a.1))||a

Test:

    log str R [(λ:(λ:[2 [2 [2 1]]])), (λ:(λ:[2 [2 1]]))]
    # Ouputs: {"λ":{"λ":[2,[2,[2,[2,[2,[2,[2,[2,1]]]]]]]]}}

Which is `2^3=9`, as stated on OP.