Initializer vs Constructor

__init__ is called with an already built up instance of the object as first parameter (normally called self, but that's just a parameter name).

__new__ instead is called passing the class as first parameter and is expected to return an instance (that will be later passed to __init__).

This allows for example __new__ to return an already-existent instance for value-based objects that are immutable and for which identity shouldn't play a role.

In essence, __new__ is responsible for creating the instance (thus, it may be accurate to say that it is the constructor, as you've noted) while __init__ is indeed a way of initializing state in an instance. For example, consider this:

class A(object):

    def __new__(cls):
        return object.__new__(cls)

    def __init__(self):
        self.instance_method()

    def instance_method(self):
        print 'success!'

newA = A()

Notice that __init__ receives the argument self, while __new__ receives the class (cls). Since self is a reference to the instance, this should tell you quite evidently that the instance is already created by the time __init__ gets called, since it gets passed the instance. It's also possible to call instance methods precisely because the instance has already been created.

As to your second question, there is rarely a need in my experience to use __new__. To be sure, there are situations where more advanced techniques might make use of __new__, but those are rare. One notorious example where people might be tempted to use __new__ is in the creation of the Singleton class (whether that's a good technique or not, however, isn't the point).

For better or worse, you basically get to control the process of instantiation, and whatever that might mean in your specific situation.