Есть несколько способов.
1. При создании записи сразу сохранять данные адреса, предварительно получив их из API Яндекса или другого сервиса.
2. Если данных адреса по координатам нет, то периодически их заполнять при выполнении некоего скрипта по задаче cron. Сам скрипт опять же обращается в API Яндекса, получает адрес и сохраняет в базу.
3. Иметь некую картографическую базу данных, в которой есть адреса и координаты. С помощью не хитрого SQL запроса можно получить адрес. Тут подойдет база ОСМ (OpenStreetMap).
В вашем случае будет правильней сопоставить 1 и 2 способ вместе. Т.е. в момент создания записи (например на html форме) запрашивать координаты у пользователя и по ним заполнять поле с адресом. Если произошла ошибка, то сохраняем только координаты, потом по крону их заполним.
Третий способ чреват тем, что база ОСМ очень большая и далеко не все данные правильны. Зато это бесплатно. API Яндекса при большом количестве запросов блокируется и требует денег.