ChessMetric - Topcoder Challenge
Since you have decided to go the way of the specialized object for your board, there are two obvious improvements. One is to use Python magic methods to have a more pythonic notation. The other is to offload the bounds checking to this specialized class. For instance:

class Board(object):
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.board = [[0] * cols for row in range(rows)]

    def __getitem__(self, index):
        row, col = index
        if 0 &lt;= row &lt; self.rows and 0 &lt;= col &lt; self.cols:
            return self.board[row][col]
        return 0

    def __setitem__(self, index, value):
        row, col = index
        if 0 &lt;= row &lt; self.rows and 0 &lt;= col &lt; self.cols:
            self.board[row][col] = value


This simple class lets you use typical Python indexing with square brackets to access the board, and silently handles out of bounds access.

You may also want to be a little terser about generating your moves. This is one of many options:

def kingknight_moves(start):
    row, col = start
    dest = []
    for dr in range(-2, 3):
        cols = (1, -1) if abs(dr) != 1 else range(-2, 3)
        for dc in cols:
            dest.append((row + dr, col + dc))
    return dest


I'm also going to write a function to advance the board one move:

def advance_board(board):
    new_board = Board(board.rows, board.cols)
    for row in range(board.rows):
        for col in range(board.cols):
            count = board[row, col]
            if count:
                for dest in kingknight_moves((row, col)):
                    new_board[dest] += count
    return new_board


This is pretty much the same you are doing, modulo a nicer syntax.

Now to the meat of the problem... A naive approach like the one you have implemented works:

def chess_metric_naive(size, src, dst, moves):
    board = Board(size, size)
    board[src] = 1

    for move in range(moves):
        board = advance_board(board)

    return board[dst]


But is indeed kind of slow for the largest of the problems posed:

%timeit chess_metric_naive(100, (0, 0), (0, 99), 50)
1 loops, best of 3: 3.7 s per loop


If you were to time each of your iterations advancing the board one move, you would notice that they get progressively slower, as more and more cells are non-zero and contribute to their neighbors. One way of mitigating this effect is to, rather than completing all moves from the source towards the destination, do half of them like this, and the rest from destination to source. If there are \$m\$ ways of getting from the source to a certain cell in half the moves, and \$n\$ ways of getting from the destination to the same cell in the remaining moves, then there are \$mn\$ ways of getting from source to destination. You could implement this like:

def chess_metric(size, src, dst, moves):
    src_board = Board(size, size)
    src_board[src] = 1
    dst_board = Board(size, size)
    dst_board[dst] = 1

    for move in range(moves // 2):
        src_board = advance_board(src_board)
        dst_board = advance_board(dst_board)

    if moves % 2:
        src_board = advance_board(src_board)

    total = 0
    for row in range(size):
        for col in range(size):
            total += src_board[row, col] * dst_board[row, col]

    return total


And it turns out to be substantially (3x) faster:

%timeit chess_metric(100, (0, 0), (0, 99), 50)
1 loops, best of 3: 1.2 s per loop


We can do even better though: an alternative approach is to use something akin to a branch and bound approach. We know that the maximum distance that our made up chess piece can move is \$\sqrt 5\$, so we need not consider cells that are further from the destination more than that value times the number of moves left. A possible approach is to create a board holding minimum number of moves to get to the destination from any other cell:

def moves_lower_bound(rows, cols, dst):
    from math import sqrt, ceil
    dst_row, dst_col = dst
    board = Board(rows, cols)
    for row in range(rows):
        row2 = row - dst_row
        row2 *= row2
        for col in range(cols):
            col2 = col - dst_col
            col2 *= col2
            dist2 = row2 + col2
            # rounded up int division dist2 // 5
            board[row, col] = int(ceil(sqrt(dist2) / sqrt(5)))
    return board


With the aid of this auxiliary board, we can prune the cells that cannot add to the final result whenever we advance the board:

def advance_and_prune_board(board, bounds, moves_left):
    new_board = Board(board.rows, board.cols)
    for row in range(board.rows):
        for col in range(board.cols):
            count = board[row, col]
            if count and bounds[row, col] &lt;= moves_left:
                for dest in kingknight_moves((row, col)):
                    new_board[dest] += count     
    return new_board


Putting all this together:

def chess_metric_bb(size, src, dst, moves):
    board = Board(size, size)
    board[src] = 1
    bounds = moves_lower_bound(size, size, dst)

    for move in range(moves):
        board = advance_and_prune_board(board, bounds, moves - move)

    return board[dst]


We get close to a 9x improvement over the simpler approach:

%timeit chess_metric_bb(100, (0, 0), (0, 99), 50)
1 loops, best of 3: 424 ms per loop