Всеволод Руднев родился 31 августа 1955 года в городе-крепости Динамюнде, Латвия. После окончания гимназии в 1872 году поступил в Морское училище в Петербурге. На действительную службу поступил во время учебы в училище. С 1873 по 1875 годы участвовал в учебных плаваниях по Балтийскому морю. Получил звание старшего унтер-офицера. После сдачи выпускных экзаменов на отлично удостоился Нахимовской премии. В 1976 году получил воинское звание «гардемарин».

Руднев назначен на учебный фрегат «Петропавловск» матросом. Участвовал в заграничном учебном плавании. Это первый дальний поход. Кроме обязанностей матроса, нес офицерскую вахту, на практике обучаясь ремеслу моряка. В 1877 году получил чин мичмана. С этого времени находился на годичных курсах во флотской стрелковой роте. В 1880 году служил на крейсере «Африка». Крейсер прибыл на Дальний Восток, а затем совершил кругосветное путешествие. Позднее Руднев стал командиром 7-й роты на крейсере. В 1882 году стал лейтенантом. 

После возвращения из кругосветного путешествия Всеволод Руднев продолжал плавать по Балтийскому морю, а в 1886 году участвовал в заграничном плавании. В 1888 году Российский флот получил первый паровой военный транспорт «Петр Великий». Привести его из Франции поручено Рудневу. C 1 августа 1889 года находился в заграничном плавании на крейсере «Адмирал Корнилов». Участвовал в маневрах Тихоокеанского флота, стал старшим офицером корабля. В 1890 году вернулся в Кронштадт. В 1891 году последовательно являлся командиром миноносца «Котлин», портового парохода «Работник», старшим офицером броненосца «Гангут».

В 1893 году Всеволод Федорович Руднев получил чин капитана 2-го ранга и стал старшим офицером эскадренного броненосца «Император Николай I». Броненосец отправился в Грецию, чтобы присоединиться к группе русских кораблей. Около года броненосец провел в территориальных водах Греции. Затем «Император Николай I» находился в кругосветном плавании. Вернувшись в Кронштадт, стал командиром броненосца береговой обороны «Адмирал Грейг», а затем назначен командиром миноносца «Выборг».

В декабре 1897 года Всеволод Федорович стал командиром канонерской лодки «Гремящий», на которой совершил свое первое самостоятельное кругосветное плавание. Позднее назначен командиром броненосца береговой обороны «Чародейка». В начале июня 1900 года Российский флот получил эскадренный миноносец «Скат», построенный для России. Руднев привел его из порта города Эльбинга в Германии в Кронштадт. Затем Руднев становится старшим помощником командира порта в Порт-Артуре и получил чин капитана 1-го ранга.

В декабре 1902 года Всеволод Руднев назначен командиром крейсера «Варяг». Накануне войны «Варяг» направлен в нейтральный корейский порт Чемульпо. Утром 9 февраля 1904 года Руднев получил ультиматум японского контр-адмирала Сотокити Уриу с требованием покинуть рейд до полудня.  Руднев принял решение прорываться из залива. В результате боя крейсер получил повреждение и командир принял решение вернуться в Чемульпо и уничтожить корабль. После своза команды на нейтральные корабли, «Варяг» затоплен путем открытия кингстонов. После возвращения на родину Руднев награжден орденом Святого Георгия 4-й степени, получил звание флигель-адъютанта и стал командиром эскадренного броненосца «Андрей Первозванный».

В ноябре 1905 года Руднев отказался принять дисциплинарные меры против революционно настроенных матросов своего экипажа. Впоследствии уволен в отставку с производством в контр-адмиралы. В 1907 году японский император Муцухито в знак признания героизма русских моряков направил Рудневу орден Восходящего солнца II степени. Последние годы Всеволод Федорович жил в своей усадьбе в Тульской губернии. Умер 20 июля 1913 года. Похоронен возле церкви Казанской Богоматери в Тульской области.

Память