Всеволод Потеминский — сын псаломщика села Ляменье Никольского уезда Вологодской губернии. В 1890 году 20-летний Всеволод Потеминский окончил 3 класса Вологодской духовной семинарии. 21 ноября 1890 года был рукоположен во диакона епископом Великоустюжским Иоанникием (Казанским), определен к Крестовоздвиженской церкви села Симоноволомского (приходская церковь на месте упраздненного Симоноволомского монастыря).
В 1891-1900 гг. был учителем Симоноволомской народной начальной школы.
17 апреля 1900 года по прошению переведен к Введенской церкви в Никольском уезде Вологодской губернии, затем переведен в Никольскую церковь с. Семуково Яренского уезда Вологодской губернии.
3 июня 1903 г. рукоположен во священника епископом Вологодским Алексием (Соболевым).
С 1903 г. — законоучитель Семуковской церковно-приходской школы, с 1906 г. — член попечительского совета, с 1910 г. — законоучитель Кырсинского земского начального училища.
Собрал большую библиотеку, в т. ч. много книг по агрономии, открыл в своем селе школу, где преподавал по собственным учебникам; пользовался авторитетом у прихожан, которые несколько раз защищали его от ареста. Но в 1928 году был арестован, лишен избирательных прав, но в том же году продолжил священническое служение. В 1934 и 1936 годах также был судим. Был выселен с семьей из дома.
На церковь были наложены непосильные налоги. Зимой 1937 г. Семуковская Никольская церковь была закрыта, в здании хотели открыть клуб, неоднократно пытались уничтожить кресты, вырезанные на стенах храма, но кресты чудесным образом появлялись вновь. О. Всеволод протестовал против закрытия церкви.
7 августа 1937 года был арестован (был обманом вызван якобы на крестины) и заключен в тюрьму НКВД г. Сыктывкара. Из обвинительного заключения: «Реакционно настроенный тихоновец, участвует в к/р сборищах, ведет активную а/с агитацию, выражающуюся в протестах против закрытия церкви, против сборов денег на уплату налога с церкви... систематически проводил контрреволюционную деятельность, направленную против мероприятий сов. власти. В июне месяце 1937 г. распространял провокационные слухи о войне и падении сов. власти. Проводил подготовку к выборам в советы, выставлял кандидатуры из числа контрреволюционных элементов и агитировал среди населения за поддержку этих кандидатур».
Следствие было проведено с грубейшими нарушениями: право на защиту не обеспечено, обвинительное заключение не мотивировано и прокурором не утверждено. Священник виновным себя не признал.
16 сентября 1937 года Тройкой при УНКВД Коми АССР был приговорен к расстрелу.
Расстрелян 19 сентября 1937 года в окрестностях г. Сыктывкара.