Japt v2.0a0, 9 8 bytes

nVîX WîX

Try it

APL, 10 bytes

{⍺⍺[⍵⍵⍳⍵]}

This is an APL operator. In APL, ⍵ and ⍺ are used to pass values, while ⍵⍵ and ⍺⍺ are usually used to pass functions. I'm abusing this here to have 3 arguments. ⍺⍺ is the left argument, ⍵⍵ is the "inner" right argument, and ⍵ is the "outer" right argument.

Basically: ⍺(⍺⍺{...}⍵⍵)⍵

Then all that's needed is ⍳ to find the positions of the input string in the "from" table, and then use [] to index into the "to" table with these positions.

Example:

    ('012345'{⍺⍺[⍵⍵⍳⍵]}'abcdef')'abcabc'
012012

Python 2, 115 114 106 105 94 bytes

Golfing suggestions welcome. Try it online!

Edit: -9 bytes thanks to mbomb007. -2 bytes thanks to FlipTack.

def a(n,f,t,d,z=0,s=''):
 for i in n:z=z*f+d.find(i)
 while z:s=d[z%t]+s;z/=t
 print s or d[0]

Ungolfed:

def arbitrary_base_conversion(num, b_from, b_to, digs, z=0, s=''):
    for i in num:
        z = z * b_from + digs.index(i)
    while z:
        s = digs[z % b_to] + s
        z = z / t
    if s:
        return s
    else:
        return d[0]

Ruby, 113 112 105 98 97 95 87 bytes

I sort of double-posted my Python answer (somehow), so here's a Ruby answer. Seven more bytes thanks to manatwork, another byte thanks to Martin Büttner, and 8 more bytes thanks to cia_rana.

->n,f,t,d{z=0;s='';n.chars{|i|z=z*f+d.index(i)};(s=d[z%t]+s;z/=t)while z>0;s[0]?s:d[0]}

Ungolfed:

def a(n,f,t,d)
  z=0
  s=''
  n.chars do |i|
    z = z*f + d.index(i)
  end
  while z>0 
    s = d[z%t] + s
    z /= t
  end
  if s[0]   # if n not zero
    return s
  else
    return d[0]
  end
end

JavaScript (ES6), 140 bytes

(s,f,t,m)=>[...s].map(c=>{c=m.indexOf(c);for(i=0;c||i<r.length;i++)r[i]=(n=(r[i]|0)*f+c)%t,c=n/t|0},r=[0])&&r.reverse().map(c=>m[c]).join``

Unlike @Mwr247's code (which uses base-f arithmetic to divide s by t each time, collecting each remainder as he goes) I use base-t arithmetic to multiply the answer by f each time, adding each digit of s as I go.

Ungolfed:

function base(source, from, to, mapping) {
    result = [0];
    for (j = 0; j < s.length; s++) {
        carry = mapping.indexOf(s[j]);
        for (i = 0; carry || i < result.length; i++) {
            next = (result[i] || 0) * from + carry;
            result[i] = next % to;
            carry = Math.floor(next / to);
         }
    }
    string = "";
    for (j = result.length; j --> 0; )
        string += mapping[result[j]];
    return string;
}

JavaScript (ES6), 175 bytes

(s,f,t,h)=>eval('s=[...s].map(a=>h.indexOf(a));n=[];while(s.length){d=m=[],s.map(v=>((e=(c=v+m*f)/t|0,m=c%t),e||d.length?d.push(e):0)),s=d,n.unshift(m)}n.map(a=>h[a]).join``')

Figured it's been long enough now that I can submit the one I made to create the examples. I may try and golf it down a bit better later.

CJam, 34 bytes

0ll:Af#lif{@*+}~li:X;{XmdA=\}h;]W%

Input format is input_N alphabet input_B output_B each on a separate line.

Run all test cases.

Explanation

0     e# Push a zero which we'll use as a running total to build up the input number.
l     e# Read the input number.
l:A   e# Read the alphabet and store it in A.
f#    e# For each character in the input number turn it into its position in the alphabet,
      e# replacing characters with the corresponding numerical digit value.
li    e# Read input and convert to integer.
f{    e# For each digit (leaving the base on the stack)...
  @*  e#   Pull up the running total and multiply it by the base.
  +   e#   Add the current digit.
}
~     e# The result will be wrapped in an array. Unwrap it.
li:X; e# Read the output base, store it in X and discard it.
{     e# While the running total is not zero yet...
  Xmd e#   Take the running total divmod X. The modulo gives the next digit, and
      e#   the division result represents the remaining digits.
  A=  e#   Pick the corresponding character from the alphabet.
  \   e#   Swap the digit with the remaining value.
}h
;     e# We'll end up with a final zero on the stack which we don't want. Discard it.
]W%   e# Wrap everything in an array and reverse it, because we've generated the 
      e# digits from least to most significant.

This works for the same byte count:

L0ll:Af#lif{@*+}~li:X;{XmdA=@+\}h;

The only difference is that we're building up a string instead of collecting everything on the stack and reversing it.

C (function) with GMP library, 260

This turned out longer than I'd hoped, but here it is anyway. The mpz_* stuff really eats up a lot of bytes. I tried #define M(x) mpz_##x, but that gave a net gain of 10 bytes.

#include <gmp.h>
O(mpz_t N,int t,char*d){mpz_t Q,R;mpz_inits(Q,R,0);mpz_tdiv_qr_ui(Q,R,N,t);mpz_sgn(Q)&&O(Q,t,d);putchar(d[mpz_get_ui(R)]);}F(char*n,int f,int t,char*d){mpz_t N;mpz_init(N);while(*n)mpz_mul_ui(N,N,f),mpz_add_ui(N,N,strchr(d,*n++)-d);O(N,t,d);}

The function F() is the entry-point. It converts the input string to an mpz_t by successive multiplications by the from-base and addition of the index of the given digit in the digit list.

The function O() is a recursive output function. Each recursion divmods the mpz_t by the to-base. Because this yields the output digits in reverse order, the recursion effectively allows the digits to be stored on the stack and output in the correct order.

Test driver:

Newlines and indenting added for readability.

#include <stdio.h>
#include <string.h>

#include <gmp.h>
O(mpz_t N,int t,char*d){
  mpz_t Q,R;
  mpz_inits(Q,R,0);
  mpz_tdiv_qr_ui(Q,R,N,t);
  mpz_sgn(Q)&&O(Q,t,d);
  putchar(d[mpz_get_ui(R)]);
}
F(char*n,int f,int t,char*d){
  mpz_t N;
  mpz_init(N);
  while(*n)
    mpz_mul_ui(N,N,f),mpz_add_ui(N,N,strchr(d,*n++)-d);
  O(N,t,d);
}

int main (int argc, char **argv) {
  int i;

  struct test_t {
    char *n;
    int from_base;
    int to_base;
    char *digit_list;
  } test[] = {
    {"1010101", 2, 10, "0123456789"},
    {"0001010101", 2, 10, "0123456789"},
    {"85", 10, 2, "0123456789"},
    {"1010101", 10, 2, "0123456789"},
    {"bababab", 2, 10, "abcdefghij"},
    {"10", 3, 2, "0123456789"},
    {"<('.'<)(v'.'v)(>'.'>)(^'.'^)", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? "},
    {"~~~~~~~~~~", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? "},
    {"9876543210123456789", 10, 36, "0123456789abcdefghijklmnopqrstuvwxyz"},
    {"ALLYOURBASEAREBELONGTOUS", 62, 10, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"},
    {"howmuchwoodcouldawoodchuckchuckifawoodchuckcouldchuckwood", 36, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? "},
    {"1100111100011010101010101011001111011010101101001111101000000001010010100101111110000010001001111100000001011000000001001101110101", 2, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? "},
    {0}
  };

  for (i = 0; test[i].n; i++) {
    F(test[i].n, test[i].from_base, test[i].to_base, test[i].digit_list);
    puts("");
  }

  return 0;
}

Seriously, 50 bytes

0╗,╝,2┐,3┐,4┐╛`4└í╜2└*+╗`MX╜ε╗W;3└@%4└E╜@+╗3└@\WX╜

Hex Dump:

30bb2cbc2c32bf2c33bf2c34bfbe6034c0a1bd32c02a2bbb60
4d58bdeebb573b33c0402534c045bd402bbb33c0405c5758bd

I'm proud of this one despite its length. Why? Because it worked perfectly on the second try. I wrote it and debugged it in literally 10 minutes. Usually debugging a Seriously program is an hour's labor.

Explanation:

0╗                                                  Put a zero in reg0 (build number here)
  ,╝,2┐,3┐,4┐                                       Put evaluated inputs in next four regs
             ╛                                      Load string from reg1
              `         `M                          Map over its chars
               4└                                   Load string of digits
                 í                                  Get index of char in it.
                  ╜                                 Load number-so-far from reg0
                   2└*                              Multiply by from-base
                      +                             Add current digit.
                       ╗                            Save back in reg0
                          X                         Discard emptied string/list.
                           ╜                        Load completed num from reg0
                            ε╗                      Put empty string in reg0
                              W                W    While number is positive
                               ;                    Duplicate
                                3└@%                Mod by to-base.
                                    4└E             Look up corresponding char in digits
                                       ╜@+          Prepend to string-so-far.
                                                      (Forgetting this @ was my one bug.)
                                          ╗         Put it back in reg0
                                           3└@\     integer divide by to-base.
                                                X   Discard leftover 0
                                                 ╜  Load completed string from reg0
                                                    Implicit output.