В википедии даже, как оказалось, есть список этих построенных церквей:
Изначально Архангельский храм был деревянным. Являясь единственным действующим храмом города в поствоенный период, он не мог вмещать всех многочисленных верующих. Но строительство новой церкви не было одобрено властями. Тогда прихожане под предлогом сбора средств на капитальный ремонт, собрали деньги на стройматериалы и начали строительство нового каменного храма рядом с деревянным. Об этом факте местные недоброжелатели доложили в столицу. На что из Москвы была прислана комиссия для проверки сего факта. Но об этом горожанам стало известно заранее (здесь усматривают божий промысел), и до приезда комиссии начатое сооружение было разобрано, а материалы были спрятаны во дворах прихожан. Не заметив этого, комиссия вернулась в столицу. А прихожане довели строительство до конца. Таким образом в 1982 г. в городе появился первый каменный храм.
Да строили, и хотя в большинстве своем это были деревянные постройки, есть строительство и нескольких храмов из камня. Наиболее значимым из которых Был Храм Михаила в Магнитогорске