• You can remove some nesting by returning early.
• There are other changes that could bring down memory usage, but in general using generators instead of creating full lists is beneficial (xrange below).
• Multiplying a list is a bit more concise then the equivalent list comprehension ([None] * 4), but beware of sharing if you were to nest that ([[None] * 4] * 4 contains the same list four times).
• I've added _map_tiles method to extract the shared "iterate over all map tiles" behaviour.
• The smoothing function is a bit weird in the sense that the two tests can easily be merged into a single case and an addition. I don't know if you wanted maybe a more complex behaviour there, but this is equivalent and less confusing.
• I'm also not fond of the IndexError handling, although I can see why this is easier, as you don't have to bother with generating only valid coordinates, even then the fact that you abort early and don't check each of the four cases individually is a bit frustrating to look at.
• Since you handle quite a lot of coordinates I'd maybe suggest that, if you were to continue on this, to introduce more abstractions on top of the nested list representation in order to handle both the [x][y] syntax, as well as indexing by coordinate pairs, i.e. [(x, y)], via a Map class (or so). That way you can simplify other code a lot, e.g. via generating a list of coordinates, zip with new values, then apply them all at once; basically it would facilitate a more functional approach. Same, for example, by generating the four coordinates around a tile in one call, returning [(x, y+1), ...].

All in all:

"""
A basic library containing a class for
generating basic terrain data.
"""
from random import randint


class Terrain(object):
    """
    Terrain object for storing and generating
    "realistic" looking terrain in an array.
    """
    def __init__(self,
                 min_height, max_height,
                 min_change, max_change,
                 data_width, data_height,
                 seeding_iterations, generation_iterations,
                 smoothing=True, replace_NoneTypes=True):
        self.min_height = min_height
        self.max_height = max_height
        self.min_change = min_change
        self.max_change = max_change
        self.data_width = data_width
        self.data_height = data_height
        self.seeding_iterations = seeding_iterations
        self.generation_iterations = generation_iterations
        self.smoothing = smoothing
        self.replace_NoneTypes = replace_NoneTypes
        self.world_data = None

    def _assert_arguments(self):
        """
        Assert the provided arguments to __init__ and
        make sure that they are valid.
        """
        assert self.max_height > self.min_height, "Maximum height must be larger than minimum height."
        assert self.max_change > self.min_change, "Maximum change must be larger than minimum change."
        assert self.data_width > 0, "Width must be greater than zero."
        assert self.data_height > 0, "Height must be greater than zero."
        assert self.seeding_iterations > 0, "Seeding iterations must be greater than zero."
        assert self.generation_iterations > 0, "Generation iterations must be greater than zero."

    def _generate_inital_terrain(self):
        """
        Initalizes the self.world_data array with a
        NoneType value.
        """
        self.world_data = [[None] * self.data_width
                           for _ in xrange(self.data_height)]

    def _seed_terrain(self):
        """
        "Seeds" the terrain by choosing a random spot
        in self.world_data, and setting it to a random
        value between self.min_height and self.max_height.
        """
        for _ in xrange(self.seeding_iterations):
            random_x = randint(0, self.data_width - 1)
            random_y = randint(0, self.data_height - 1)
            self.world_data[random_x][random_y] = randint(
                self.min_height, self.max_height
            )

    def _map_tiles(self, function):
        for index_y, tile_row in enumerate(self.world_data):
            for index_x, tile in enumerate(tile_row):
                function(index_y, tile_row, index_x, tile)

    def _generate_iterate(self):
        """
        Generates the terrain by iterating n times
        and iterating over the world data and changing
        terrain values based on tile values.
        """
        def generate_tile(index_y, tile_row, index_x, tile):
            if tile is None:
                return

            rand_values = [tile + randint(self.min_change,
                                          self.max_change)
                           for _ in xrange(4)]

            try:
                if self.min_height <= tile <= self.max_height:
                    self.world_data[index_y + 1][index_x] = rand_values[0]
                    self.world_data[index_y - 1][index_x] = rand_values[1]
                    self.world_data[index_y][index_x + 1] = rand_values[2]
                    self.world_data[index_y][index_x - 1] = rand_values[3]

            except IndexError:
                pass

        for _ in xrange(self.generation_iterations):
            self._map_tiles(generate_tile)

    def _replace_NoneTypes(self):
        """
        Iterates over the world data one last time
        and replaces any remaining NoneType's with
        the minimum height value.
        """
        def set_min_height(index_y, tile_row, index_x, tile):
            if tile is None:
                self.world_data[index_y][index_x] = self.min_height

        self._map_tiles(set_min_height)

    def _smooth_terrain(self):
        """
        "Smoothes" the terrain a into slightly more
        "realistic" landscape.
        """
        threshold = 3
        factor = 2

        def smooth_tile(index_y, tile_row, index_x, tile):
            def smooth_single(other_tile_y, other_tile_x):
                other_tile = self.world_data[other_tile_y][other_tile_x]

                if other_tile - tile >= threshold:
                    self.world_data[other_tile_y][other_tile_x] -= factor

            try:
                smooth_single(index_y - 1, index_x)
                smooth_single(index_y + 1, index_x)
                smooth_single(index_y, index_x + 1)
                smooth_single(index_y, index_x - 1)

            except IndexError:
                pass

        self._map_tiles(smooth_tile)

    def generate_data(self):
        """
        Puts together all the functions required
        for generation into one container for running.
        """
        self._assert_arguments()
        self._generate_inital_terrain()
        self._seed_terrain()
        self._generate_iterate()
        if self.replace_NoneTypes:
            self._replace_NoneTypes()
        if self.smoothing:
            self._smooth_terrain()

    def return_data(self):
        """
        Returns the world data as a list.
        """
        return self.world_data

    def debug_data(self):
        """
        Prints out the height values in self.world_data
        for debugging and visuals.
        """
        for tile_row in self.world_data:
            print ' '.join(str(height_value) for height_value in tile_row)


if __name__ == "__main__":
    terr = Terrain(1, 8, -1, 1, 20, 20, 3, 10, smoothing=True)
    terr.generate_data()
    terr.debug_data()