Выпускник Санкт-Петербургской государственной консерватории по классам композиции (преп.- Борис Тищенко) и дирижирования (преп.-Михаил Орехов и Михаил Кукушкин), Всеволод Полонский продолжил свое обучение в Лионской Национальной Консерватории (класс Жильбера Ами) и в Парижской Национальной Консерватории, где занимался в классе Яноша Фюрста и участвовал в мастер-классах Йормы Панулы, Джона Нельсона, Дэвида Робертсона. Также совершенствовался в Американской Консерватории в Фонтэнбло и в Европейской Музыкальной Академии фестиваля Экс-ан-Прованса (класс Филиппа Манури).

Лауреат 48-го Международного конкурса Молодых дирижеров (Безансон, 2003, Специальная Зрительская премия), VII Международного Конкурса имени Грегора Фительберга (2003, Специальная премия PWM за лучшее исполнение современного польского произведения), Международного конкурса дирижеров в Кордобе (Испания, 2006, Первая премия), 28-го Международного конкурса Masterpalayers (Швейцария, 2008, Первый Почетный диплом).

В апреле 2010 года Всеволод Полонский получил театральную премию «Золотая маска» за лучшую работу дирижера в мьюзикле Мишеля Леграна «Шербурские зонтики», поставленного в музыкальном театре «Карамболь» (Санкт-Петербург). За эту же работу дирижер так же номинирован на премию фестиваля «Музыкальное сердце России».

Сочинения Всеволода Полонского удостоились Первых премий на шести международных композиторских конкурсах (в том числе: конкурс Анри Дютийо (1999) и конкурс Квартета Молинари (2002), они исполняются в программах престижных международных фестивалей и в отдельных концертах во многих странах Европы и Северной Америки. Как театральный композитор сотрудничал с Малым Драматическим театром — театром Европы (художественный руководитель - Лев Додин), многочисленными театральными антрепризами. В 2000 году написал детский мьюзикл «Айболит и Бармалей» для Санкт-Петербургского ТЮЗа (поставка Сергея Каргина).

В настоящее время Всеволод Полонский возглавляет оркестр «La Sinfonietta» в г. Дуэ (Франция) и камерный оркестр «Mеtamorphoses» в Париже. В течение 6 лет возглавлял Хор и Оркестр Высших Школ города Парижа. В 2008 году парижский ансамбль “Armеde”, специализирующийся на исполнении музыки начала ХХ века, назначил Всеволода Полонского своим музыкальным руководителем.

Сотрудничает со многими оркестрами Санкт-Петербурга, оркестром Иль-дё-Франс, Лионским Национальным оркестром, оркестром Театра Лисеу (Барселона, Испания), Оркестром Кордобы (Испания), Силезским филармоническим оркестром, Ярославским симфоническим оркестром, Крымским Национальным оркестром, а также многочисленными ансамблями современной музыки.