defin

Маленькое обновление или большое - нет разницы, тут важно чтобы подписи (ключи) совпадали
Могу сказать точно про андроид: заменить полностью можно, главное чтобы у вас остались ключи и пароли к ним, которые подписывают apk для отправки в Google Play Store
Про iOS: могу ошибаться, но там xcode просит войти в аккаунт разработчика внутри xcode, сам вытаскивает с инете ключи, подписывает готовое приложение и отправляет в App Store. То есть в этом случае у вас должен быть доступ к аккаунту разработчика, с которого выкладывалось приложение и вы сможете заменить.
Есть нюанс с Android, если в новом приложение вы добавите НОВЫЕ зависимости от доступа к телефону пользователя (доступ к карте памяти, камере, интернету, etc), то приложение автоматически не обновится, а потребует дополнительных действий от пользователя - подтвердить согласия на новый уровень доступа приложения.

Никакая замена не возможна! Просто создаете новую версию этого же приложения и заливаете новую сборку. Никого просить установить заново не нужно. Если у пользователя в настройках прописано автоматическое обновление, то оно автоматом обновится. Если ручное, то у него появится предложение обновить Ваше приложение.

Если представить это как новую версию того же самого приложения — проблем быть не должно.

В пиковые моменты может приходить до 10 000 таких вот обращений в секунду (проектируемая нагрузка). Но волнами, т.е. отправили мы, условно, 100 000 сообщений, их начали читать и посыпались оповещения о прочтении на сервер.

Буквально сейчас тестирую высокие нагрузки.
Сетевой стек Linux - говно-говном. Чтобы получать 30 000 в секунду (на виртуалке) нужно отдать ему целиком 1 ядро процессора на 100%. И это не считая того, что нужно еще обработать информацию и отдать ответ. Отдача тоже грузит ядро почти на полную, но чуть-чуть поменьше все же, чем прием.

На реальном железе не на виртуальном - народ утверждает, что можно получать примерно в 10 раз больше. Но это dedicated.

Так что 100 000 в секунду - это будет очень не просто.

Если нагрузка рваная - то специальное облако, автомасштабируемое - вас спасет.
Иначе - придется серьезно разбираться как оптимизировать, как распараллелить.

Посмотрите в сторону облачных решений.

Например Google AppEngine Datastore - может масштабироваться практически безгранично. К тому же очереди бесплатно. Можно класть сообщение о прочтении в очередь и обновлять базу пачкой. Клиенту будет ответ в течении 100-500 миллисекунд. 100 000 сообщений можно будет обработать за пару секунд-минуту в зависимости от того какой лимит по количеству инстансов будет.

Я использую AppEngine Go standard environment для своего приложения по учёту долгов https://DebtsTracker.io/ и очень доволен.

Go выбрал чтобы инстансы стартовали очень быстро.

Standard, а не Flexible чтобы не управлять самому масштабированием. Хотя сейчас уже и flexible может автоматически масштабироваться.