Как добавить поле в высоконагруженную базу в таблицу на продакшене где 100 миллионов записей?
Могу ответить про postgresql.

без ее блокировки
Именно в такой постановке вопроса - никак.

С короткой блокировкой (доли секунд) - другое дело. Принципиально зависит от конкретного alter table и версии базы
Простой alter table foo add column col; - ставите statement_timeout to '100ms' и вносите как есть.
alter table foo add column col default const - после pg11 см. выше, до - интересное приключение
Если default не константа - сначала внесите как default null, затем обновляете частями. как в процессе до pg11.
Как вариант для MySQL можно заюзать утилиту от гитхаб https://github.com/github/gh-ost