Если вы найдёте в Москве место, где такую справку дают, сможете её получить и поделетесь со всеми этим опытом -- будет здорово. Насколько я знаю ЗАГСы таких справок не дают.
Собственно, и Консульство в Лиссабоне такую справку не даёт -- оно заверяет вашу подпись на личном заявлении о брачной правоспособности (это заявление сразу на двух языках, поэтому отдельного перевода и его заверения не требует). И такое заявление подаётся в консерваторию португальскую (ЗАГС).
Поскольку это заверение подписи на заявлении, то никакого отношения к наличию вида на жительство не имеет и Консульство оказывает эту услугу любому гражданину РФ по предъявлению паспорта. Подробности прочитайте на страничке Консульства РФ, посвящённой этому вопросу. Также на сайте Консульства РФ в Лиссабоне есть некоторые пояснения по вопросу заключения брака с участием граждан РФ на территории Португалии.