Родился 9 июля 1940 г. в Ленинграде (ныне Санкт-Петербург) в семье капитана дальнего плавания Бориса Левенштейна. Годы Великой Отечественной войны Всеволод провел с матерью в Курганской обл., отец воевал на Ленинградском фронте. В 1949 г. семья переехала в Таллин (Эстонская ССР, ныне Эстония).
В 1957 г. безуспешно пытался поступить в Театральный институт им. Бориса Щукина и Театральное училище им. М. С. Щепкина в Москве. В том же году стал курсантом судоводительского факультета Ленинградского высшего инженерного морского училища им. адмирала С. О. Макарова (ныне Государственная морская академия им. адмирала С. О. Макарова, Санкт-Петербург). Играл на кларнете в духовом оркестре училища, в 1962 г. выступал в Ленинградском джаз-октете.
После училища в 1963 г. был распределен в Эстонское морское пароходство Северо-Западного флота Министерства морского флота СССР. С весны 1963 г. занимал должности четвертого, затем третьего помощника капитана на теплоходах "Кейла" и "Верхоянск".
Весной 1964 г. уволился из состава Севзапфлота и вернулся в Ленинград, где начал работать в Ленконцерте, аккомпанируя эстрадным певцам. В 1965 г. был принят в джаз-оркестр Иосифа Вайнштейна, в составе которого стал лауреатом первого Ленинградского джазового фестиваля. Изучал английский язык, летом 1966 г. работал гидом-переводчиком в "Интуристе". С 1968 г. гастролировал по Советскому Союзу в составе оркестра Вайнштейна.
В 1972 г. руководил вокально-инструментальным ансамблем (ВИА) "Добры молодцы" при Читинской филармонии. Тогда же взял в качестве сценического псевдонима фамилию помощника капитана по политической части теплохода "Верхоянск" - Новгородцев. В 1974 г. играл в ВИА "Мифы" в г. Пушкине (Ленинград).
В ноябре 1975 г. эмигрировал из СССР вместе с первой женой, Галиной (Фаридой) Бурхановой. В течение нескольких лет они жили в Австрии и Италии. В начале 1977 г. переехали в Лондон, где Сева Новгородцев устроился на работу в Русскую службу Би-би-си, вещавшую на Советский Союз. В течение 27 лет, с 9 июня 1977 г. по 12 июня 2004 г., вел на этой радиостанции передачу "Программа поп-музыки из Лондона" (позднее - "Рок-посевы"). Программа знакомила русскоязычных радиослушателей с новинками западной популярной музыки, биографиями исполнителей и т. д. В 1980-х гг. радиоведущий Новгородцев получил широкую известность в кругах советских меломанов.
В 1980-1982 гг. Новгородцев был продюсером британской группы Icarus ("Икар"), играл в этом коллективе на саксофоне. Основал звукозаписывающую фирму Russian Roulette Records ("Рашн рулет рекордз").
В начале 1980-х гг. выступал консультантом для съемочных групп западных теле- и кинофильмов об СССР. Снимался в эпизодических ролях в британских и американских картинах ("ГУЛАГ", 1985; "Вид на убийство", 1985; "Шпионы как мы", 1985, и др.) Зачитывал дикторский текст в британской версии фильма "Рожденные в СССР. Семилетние" (1991). В 2018 г. исполнил роль антиквара в российском кинофильме "Лето" режиссера Кирилла Серебренникова.
Кроме того, Сева Новгородцев вел на Би-би-си программы "Севаоборот" (1987-2006), "БибиСева, новости с человеческим лицом" (2003-2015). В 1990-х гг. записал цикл передач "Рок-пятилетки" для "Радио 101" (Санкт-Петербург). Был одним из основателей и ведущим британской русскоязычной радиостанции "Первое русское радио" (2000-2005), ведущим программы "Севалогия" (2000-е гг.) на российском телеканале "Ностальгия". В 1995 г. выпускал в Лондоне распространявшийся в РФ иллюстрированный журнал о рок-музыке "О!" (всего было издано три номера).
Живет и работает в Лондоне.
Кавалер ордена Британской империи (2005). Лауреат российской отраслевой премии "Радиомания" (2002).
Автор книг "Рок-посевы" (на основе собственных радиопередач, в двух томах; 1995, 1997), "Секс, наркотики, рок-н-ролл" (2003), "Осторожно, люди!" (в двух томах; 2007, 2008), "Интеграл похож на саксофон" (2011).
Женат третьим браком. Первая супруга - Галина Бурханова, вторая - британская актриса Карен Розмари Крейг, третья - художница Ольга Шестакова. Сын от первого брака - Ринат. Приемная дочь - Анастасия.