Какую памятную надпись/памятник и как можно сделать для отца на его могиле, если не удается доказать родственные связи с одним из трех захороненных?

Здравствуйте. Перечень нормативных актов г. Москвы по вопросу похоронного дела достаточно обширен. Он приводится на сайте соответствующей службы:

https://ritual.mos.ru/normativnyeakty/

Водном из актов, Постановлении Правительства Москвы от 08.04.2008 № 260-ПП «О состоянии и мерах по улучшению похоронного обслуживания в городе Москве». помимо прочего указано:

2.13.  Перерегистрация  захоронения  на  другое  лицо  на  городских  кладбищах  возможна только  с  согласия  лица,  ответственного  за  захоронение, и  рассматривается в каждом  отдельном 
случае ГБУ «Ритуал» через администрацию городских кладбищ. 
Перерегистрация  захоронения  на  другое  лицо  регистрируется  в  ЕАС  «Ритуал»  и  в  книге перерегистрации  ответственности  за  захоронение  с  указанием номера участка захоронения (колумбария),  могилы (ниши), а также лица, ответственного за захоронение. 
Книга  перерегистрации  ответственности  за  захоронение  является  документом  строгой отчетности и хранится в архиве ГБУ  «Ритуал» бессрочно. 

Но этот пункт не дает надлежащей информации на случай, когда умирает ответственный за захоронение, как в Вашем случае.

Насчет перерегистрации захоронения в случае смерти ответственного на сайте есть следующая информация:

Перерегистрация захоронения в случае смерти лица, ответственного за захоронение

Перечень необходимых документов:

1. Письменное заявление лица (заявителя), на которое перерегистрируется захоронение.

2. Гербовое свидетельство о смерти (повторное свидетельство) (оригинал и копия) лица, ответственного за захоронение.

3. Документы, подтверждающие родственные отношения заявителя к одному из захороненных, а при их отсутствии – решение суда о признании факта родства (оригиналы и копии).

4. Удостоверение (паспорт) на захоронение (оригинал и копия).

<*> Перерегистрация ответственности производится на родственников захороненных с учетом степеней родства (родственники 1-7 очереди), а при отсутствии родственников какой-либо очереди право перерегистрации переходит к родственникам каждой последующей очереди.

При обращении родственников, имеющих равную степень родства (одной очереди) перерегистрация производится при наличии согласия между данными лицами и при наличии документов, подтверждающих родственные отношения к захороненному или решения суда (оригинал и копия).

При отсутствии согласия спор подлежит рассмотрению в судебном порядке.

То есть Вам не следует останавливаться на устном ответе, а направить соответствующее заявление в администрацию кладбища с документами, подтверждающими родство с одним из захороненных. В случае получения письменного отказа — обратиться в суд.

После положительного решения суда, Вы сможете сделать то, что запланировали, естественно по согласованию с администрацией, поскольку разрешение выдает она.

Приложение 1
к распоряжению Департамента
торговли и услуг города Москвы
от 2 июня 2017 г. N 170
ПОРЯДОК
ВЫДАЧИ РАЗРЕШЕНИЙ НА УСТАНОВКУ НАДМОГИЛЬНЫХ СООРУЖЕНИЙ
1. Настоящий Порядок определяет процедуру рассмотрения администрацией кладбища
заявления на выдачу разрешения на установку надмогильного сооружения (далее — разрешение) и принятия решения о выдаче такого разрешения, а также основания для выдачи, отказа в выдаче и отзыва разрешения.
2. Все работы на кладбище по установке надмогильных сооружений производятся на основании разрешения администрации кладбища.

Здравствуйте Анна.

В соответствии с Федеральным законом от 12.01.1996 N 8-ФЗ 

«О погребении и похоронном деле»

Статья 18. Общественные кладбища
 

4. Порядок деятельности общественных кладбищ определяется органами местного самоуправления. Деятельность общественных кладбищ на территориях сельских поселений может осуществляться гражданами самостоятельно.

Причина отказа — нет документов, подтверждающих родство с одним из трех захороненных

В таком случае Вы вправе установить факт родственных отношений в судебном порядке, как с приложением любых имеющихся письменных доказательств, так и с привлечением свидетелей со своей стороны, соответственно такое решение суда и будет являться документом подтверждающим родство.

ГПК РФ Статья 264. Дела об установлении фактов, имеющих юридическое значение
 

1. Суд устанавливает факты, от которых зависит возникновение, изменение, прекращение личных или имущественных прав граждан, организаций.
2. Суд рассматривает дела об установлении:
1) родственных отношений;

ГПК РФ Статья 265. Условия, необходимые для установления фактов, имеющих юридическое значение
 

Суд устанавливает факты, имеющие юридическое значение, только при невозможности получения заявителем в ином порядке надлежащих документов, удостоверяющих эти факты, или при невозможности восстановления утраченных документов.

ГПК РФ Статья 268. Решение суда относительно заявления об установлении факта, имеющего юридическое значение
 

Решение суда по заявлению об установлении факта, имеющего юридическое значение, является документом, подтверждающим факт, имеющий юридическое значение