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'

There is still an mistake in the document. I sent a pr to fix it.

New changeset 482259d0dcf27714a84cf56b93977320bea7e093 by Furkan Önder in branch 'master':
bpo-27635: Fix pickle documentation about `__new__` not being called. (GH-19269)
https://github.com/python/cpython/commit/482259d0dcf27714a84cf56b93977320bea7e093

New changeset 0abb548cc7b239fbe426ca9e00968130e53ffc98 by Miss Islington (bot) in branch '3.7':
bpo-27635: Fix pickle documentation about `__new__` not being called. (GH-19269)
https://github.com/python/cpython/commit/0abb548cc7b239fbe426ca9e00968130e53ffc98

New changeset 020f2aaaea95aef6f54ab31488926ed76017e41a by Miss Islington (bot) in branch '3.8':
bpo-27635: Fix pickle documentation about `__new__` not being called. (GH-19269)
https://github.com/python/cpython/commit/020f2aaaea95aef6f54ab31488926ed76017e41a

The problem is fixed, issue can be closed.

Ping (to close the issue).