All your bijective base are belong to us

CJam, 43

qA,s"?[a{A<":,:^+:Mf#):B;(bLa{(Bmd)M=\j\+}j

3 bytes eradicated with help from Dennis :) Try it online

Explanation:

The input is taken as bnB, concatenated into a single string.

q           read the input
A,s         make an array of numbers from 0 to 9 and convert to string
"?[a{A<"    push this string, which contains the ends of 3 character ranges:
             uppercase letters: ['A'…'[')
             lowercase letters: ['a'…'{')
             "<=>": ['<'…'?')
             they're in a special order for the symmetric difference below
:,          for each character, make a range of all characters smaller than it
:^          fold/reduce these 6 ranges using symmetric difference
+           concatenate with the digits before
:M          save in M; this is like the M from the statement,
             except it starts with a zero (for matching indexes)
f#          find the indexes in M of all characters from the input string
)           take out the last value from the array
:B;         save it in B and pop it
(           take out the first value
b           use it as a base and convert the remaining array to a number
             this works even if some of the digits are not in the "normal" range
La{…}j      calculate with memoized recursion, using an empty string for value 0
  (         decrement the number
  Bmd       divide by B and get the quotient and remainder
  )         increment the remainder (this is the last digit in bijective base B)
  M=        get the corresponding character from M
  \j        swap with the quotient, and convert the quotient recursively
  \+        swap again and concatenate

Pip, 84 80 78 bytes

m:J[,tAZLCAZ"<=>"]p:$+(m@?^b)*(m@?a)**RV,#bs:m@?cWn:px:(mn-(p:n//s-!n%s)*s).xx

GitHub repository for Pip

Algorithms adapted from the Wikipedia article. Here's the explanation for a slightly ungolfed earlier version:

                 Implicit: initialize a,b,c from cmdline args; t=10;
                 AZ=uppercase alphabet; x=""
m:               Build lookup table m:
 (J,t)             0123456789 (i.e. join(range(10)))...
 .AZ               plus A-Z...
 .LCAZ             plus lowercase a-z...
 ."<=>"            plus <=>
f:{              Define f(a,b) to convert a from bijective base b to decimal:
 $+                Sum of...
  (m@?^a)            list of index of each character of a in m
  *                  multiplied item-wise by 
  b**RV,#a           b to the power of each number in reverse(range(len(a)))
}
t:{              Define t(a,b) to convert a from decimal to bijective base b:
 x:""              Reset x to empty string (not needed if only calling the function once)
 Wa{               While a is not zero:
  p:a//b-!a%b        p = ceil(a/b) - 1 (= a//b if a%b!=0, a//b-1 otherwise)
  x:m@(a-p*b).x      Calculate digit a-p*b, look up the corresponding character in m, and
                     prepend to x
  a:p                p becomes the new a
 }
 x                 Return x
}
(t               Return result of calling t with these arguments:
 (f                Result of calling f with these arguments:
  b                  2nd cmdline arg
  m@?a)              1st cmdline arg's decimal value
 m@?c              3rd cmdline arg's decimal value
)
                 Print (implicit)

Sample run:

dlosc@dlosc:~/golf$ python pip.py bijectivebase.pip ">" "Fe" "a"
RS

Octave, 166 bytes

function z=b(o,x,n)
M=['1':'9','A':'Z','a':'z','<=>'];N(M)=1:64;n=N(n);x=polyval(N(x),N(o));z='';while x>0 r=mod(x,n);t=n;if r t=r;end;z=[M(t),z];x=fix(x/n)-(r<1);end

Multi-line version:

function z=b(o,x,n)
   M=['1':'9','A':'Z','a':'z','<=>'];
   N(M)=1:64;
   n=N(n);
   x=polyval(N(x),N(o));
   z='';
   while x>0
      r=mod(x,n);
      t=n;if r t=r;end;
      z=[M(t),z];
      x=fix(x/n)-(r<1);
   end
%end // implicit - not included above

Rather than create a map to convert a character to an index value, I just created the inverse lookup table N for ascii values 1..'z' and populated it with the indices at the appropriate values.

polyval evaluates the equation

c₁x^k + c₂x^k-1 + ... + c_kx⁰

using the decimal-converted input value as the vector of coefficients c and the original base as x. (Unfortunately, Octave's base2dec() rejects symbols out of the normal range.)

Once we have the input value in base 10, calculation of the value in the new base is straightforward.

Test driver:

% script bijecttest.m
a=b('4','','8');
disp(a);
a=b('A','16','2');
disp(a);
a=b('2','122','A');
disp(a);
a=b('3','31','1');
disp(a);
a=b('>','Fe','a');
disp(a);

Results:

>> bijecttest

1112
A
1111111111
RS
>>