A note just below object.__setstate__() documentation
https://docs.python.org/3.6/library/pickle.html#object.__setstate__
says that
"""
… the type should implement __getnewargs__() or __getnewargs_ex__() to establish such an invariant; otherwise, neither __new__() nor __init__() will be called.
"""

I believe that note about not calling __new__() was relevant in python2. I could not find case in python3 in which __new__() would not be called. And __init__() is not called anyway, as far as I understand (unless explicitly by __setstate__() or something).

Python 3.6.0a3+ (default:da9898e7e90d, Jul 27 2016, 19:51:12) 
[GCC 4.9.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> class C:
...   def __getstate__(self): return {'foo' : self.foo}
...   def __setstate__(self, state): self.foo = state['foo']
...   def __new__(cls):
...     print('__new__ is called'); return super().__new__(cls)
...   def __init__(self):
...     print('__init__ is called'); self.foo = None; super().__init__()
... 
>>> c = C(); c.foo = 'bar'
__new__ is called
__init__ is called
>>> import pickle
>>> c2 = pickle.loads(pickle.dumps(c))
__new__ is called
>>> c2.foo
'bar'