с A-записями вы далеко не уедете, для вашей схемы нужен CNAME, как в комментариях уже написали
И, если будете избавляться от A записей, надо с каждым клиентом прорабатывать отдельно: возможно, им A запись нужна потому, что в их DNS 2-го уровня зоне больше ничего нет (и у них нет других сервисов), а запись необходима для работы txt и прочих записей (например для того чтобы почта ходила). Здесь, как варианты которые можете обсудить с ними:
1. если их DNS провайдер предоставляет услугу хостинга - можно предложить направить их A запись в зоне второго уровня туда, на статический сайт с редиректом на поддомен, который, в свою очередь CNAME-ом смотрит на ваш хостинг
2. предоставить им подобный статический сервис, который вы не будете менять
3. сделать точку входа для A записей, которая не будет меняться, но и не будет содержать приложения - только балансер, направляющий трафик на ваше приложение
Еще возможно, им принципиально важно чтобы ваш сервис был на домене второго уровня. Тогда может помочь перенос с их стороны DNS хостинга на провайдера, поддерживающего ALIAS записи (он же CNAME FLATTENING у CloudFlare) - они позволяют "прописывать" в зоне 2 уровня CNAME (который динамически обновляется и преобразуется по сути в A запись) без A записи
Для переключения
Самый, наверное, простой способ контролируемо переносить на другой хостинг это уникальные таргеты для CNAME
к примеру, клиент1 получает client1.service.name который и прописывает в CNAME у себя
В случае когда нет необходимости разделять клиентов по хостингам, у вас в DNS будет запись *.service.name -> IP хостинга 1
переезжает client13: добавляем client13.service.name -> IP хостинга 2
то есть client13 смотрит на новый хостинг а все остальные - на старый
Не претендую на полноту вариантов, но похожая задача решалась при переезде (и A запись тоже была, но там от нее не избавлялись, ибо чревато переосмыслением продукта и выпиливанием фич)
Постепенное переключение решалось перекидыванием трафика на стороне LB - с помощью настройки proxy protocol. В этом случае весь трафик все равно шел через одну точку входа, но старый хостинг разгружался - клиенты постепенно перекидывались на новый, для тестирования устойчивости и мониторинга нагрузки. А затем была долгая и муторная работа команды суппорта с ожиданием клиентов которые после 10 китайского предупреждения еще не сменили IP у себя в A записях.. та еще история