Given something like:

class Foo(object):
    pass

Define Foo.__init__ to determine how to define the interior of your instance.
Define Foo.__new__ to control how you instantiate Foo
Define a metaclass type.__new__ when you want to define what Foo is at run time.

Or put another way:
__init_ decides what the inside of the house looks like, Foo.__new__ decides how you enter your new house or if you even enter a new house at all. And then Type.__new__ and company let you decide what exactly Foo should look like at run time, before you even start instantiating a new Foo.