Зачем мне гибкость Python, если мне запрещают ей пользоваться?

Таки можно. Вам же указали: есть такой метод, __call__. Будучи определен в метаклассе, он будет вызываться при создании объектов класса, вместо __new__ и __init__ вместе взятых.

Получается как-то вот так:

class cached(type):
  def __new__(cls, name, bases, dct):
    self = type.__new__(cls, name, bases, dct)
    self.cache = dict()
    return self

  def __call__(self, id, *args, **kwargs):
    if not id in self.cache:
      self.cache[id]=type.__call__(self, id, *args, **kwargs)
    return self.cache[id]

Пример: https://repl.it/MD9Z

class Animal:
    pass

class Cat(Animal):
    pass

cache = {
          (Animal, 1): 'some_animal_object',
          (Cat, 1): 'some_cat_object'
        }

print(cache[Animal, 1])
# Напечатает: some_animal_object
print(cache[Cat, 1])
# Напечатает: some_cat_object

У вас с этой проблемой нет особого выбора. Просто запретите метаклассом создавать метод meow(), лучше вы даже на уровне ниже¹ не напишете: не будет этой проблемы, будет проблема двойной инициализации, либо проблема её отсутствия, либо проблема гонки (кстати, ваш оригинальный код должен был удерживать блокировку в new и освобождать её в _fake_init (и не должен был использовать двойные подчёркивания где не надо)), либо проблема нарушения контракта «один id ссылается всегда на один и тот же объект».

¹ «На уровне ниже» можно существующему объекту и тип изменить, в т.ч. временно; при достаточном знании внутренностей CPython можно даже в процессе ничего не поломать до следующего релиза.

Варианта исправления тут два.

1. Просто откажитесь от единого хранилища всех объектов. Пусть Animal(1) и Cat(1) будут разными объектами.

   
   
2. Сделайте класс Animal "абстрактным" — пусть Animal(1) кидает ошибку если нужный объект не лежит в кеше.

Судя по описанию исходной задачи с аккаунтами, у вас по смыслу должно происходить не создание объектов типа "аккаунт", а именно получение. Конструктор же подразумевает именно создание нового. Поэтому здесь всё же лучше подходит некий репозиторий аккаунтов — он как раз может нести семантику get-or-add. И тогда можно явно запретить ситуацию, когда объект с идентификатором X неявным образом меняет свой тип.

Если смена типа во время жизни объекта нужна, то можно

1. Сделать некий метод вроде "become", но в этому случае все члены иерархии Animal должны знать друг о друге и уметь превращаться друг в друга. Опять же, будет проблема, если в одном месте объект будет сохранён как Dog с методом bark, а в другом из него сделают Cat с методом meow.
2. Можно реализовать наследование не через систему типов, а полем внутри Animal. То есть вместо объявления разных классов просто сделать поле вида 0 — Animal, 1 — Cat, 2 — Dog и в публичных методах сделать if. Это позволит в одном месте — в классе Animal — однозначно определить, можно ли добавлять meow, bark и другие методы, и можно сделать более понятную ошибку, когда метод не поддерживается текущим типом.
   На эту тему написано в Analysis Patterns Фаулера, глава 14.2.3.

Касательно замечания ZyXI про блокировку. Если надо обязательно сохранить синтаксис вызова конструктора, то можно сделать "теневую" иерархию и превратить Animal в прокси. Тогда подмена конструктора не понадобится и надо будет сделать только потоко-безопасный get-or-add для словаря-кеша:

import threading

class AnimalImpl:
    def __init__(self, id):
        self._id = id
        self._name = None

    def roar(self):
        return '{}: {}'.format(self._id, self)

    def tell_name(self):
        if self._name is None:
            raise Exception('I am nameless!')
        return self._name

    def give_name(self, name):
        self._name = name

class Animal:
    """An animal proxy

    Animal proxies with the same id are the same:

    >>> a1 = Animal(1)
    >>> a2 = Animal(1)
    >>> a1.roar() == a2.roar()
    True
    >>> a1.give_name('Baloo')
    >>> a2.tell_name()
    'Baloo'
    """
    __cache__ = dict()
    __lock__ = threading.Lock()

    def __init__(self, id):
        Animal.__lock__.acquire()
        try:
            if id in Animal.__cache__:
                self._impl = Animal.__cache__[id]
            else:
                impl = AnimalImpl(id)
                Animal.__cache__[id] = impl
                self._impl = impl
        finally:
            Animal.__lock__.release()

    def roar(self):
        self._impl.roar()

    def tell_name(self):
        return self._impl.tell_name()

    def give_name(self, name):
        self._impl.give_name(name)

if __name__ == "__main__":
    import doctest
    doctest.testmod()