Верещагин убеждался, что далеко не все воспитанники Академии, да и ее профессора мирились с мертвящей, застойной атмосферой, схоластической системой преподавания, ее эстетическими принципами. В значительной мере отошли от академизма в последние годы своей жизни К. П. Брюллов и А. А. Иванов, обратившись к живым, современным образам и сделав шаг в сторону реализма. Приблизились к реализму портретист и жанрист А. Г. Венецианов, мастер пейзажа и жанра С. Ф. Щедрин и особенно П. А. Федотов. Сильной демократической струей было пронизано творчество Т. Г. Шевченко, который внес огромный вклад в развитие украинской и русской культур не только как литератор, но и как художник. На их ярких, выразительных полотнах можно было увидеть людей из разной социальной среды, в том числе и простых тружеников.
В начале пятидесятых годов способный гравер и художник Лев Михайлович Жемчужников покинул Академию еще до окончания курса в знак протеста против ее эстетических канонов и системы преподавания. В годы пребывания в этом учебном заведении Верещагин познакомился и подружился со Львом Михайловичем, бывал у него дома, не раз беседовал с ним об искусстве и эстетике. Новый знакомый Василия Васильевича, человек прогрессивных убеждений, был близко знаком с Николаем Гавриловичем Чернышевским, дружил с Тарасом Григорьевичем Шевченко, передовыми людьми своего времени, сочувствовал им и помогал по мере своих возможностей. О трудных судьбах, несокрушимой воле этих убежденных борцов против деспотизма, вероятно, нередко заводились разговоры, когда Верещагин наведывался ко Льву Михайловичу. Поборник реализма, Жемчужников выступал в печати в защиту этого направления в искусстве и резко осуждал оторванный от жизни академизм. Такая позиция и страстная убежденность сближали его с Владимиром Васильевичем Стасовым, яростным борцом за демократизм и реализм в искусстве. Впоследствии Верещагин познакомился и подружился и со Стасовым. Влияние Жемчужникова на Василия Васильевича было несомненным.
От А. Т. Маркова Верещагин через некоторое время перешел к другому педагогу — Александру Егоровичу Бейдеману, адъюнкт-профессору, историческому живописцу. Этому переходу посодействовал Ф. Ф. Львов, продолжавший принимать участие в судьбе бывшего учащегося рисовальной школы.
Бейдеман, хотя и не был человеком последовательных демократических убеждений и иногда соглашался выполнять иконописные заказы, все же тяготел к прогрессивной творческой интеллигенции, к реализму, принципу жизненной правды в искусстве. К академической системе он относился откровенно критически и на этой почве имел серьезные трения с начальством. Александр Егорович дружил с Л. М. Жемчужниковым, высоко чтил А. И. Герцена и даже обменивался с ним корреспонденцией. А это уже могло рассматриваться как политическая крамола.
В лице Бейдемана Верещагин обрел хорошего педагога и наставника, оказавшего на юношу заметное идейное и творческое влияние. Общение с новым преподавателем не ограничивалось уроками рисования. Во время занятий велись оживленные беседы об искусстве, о подлинных и мнимых эстетических ценностях, о пороках академической системы. Адъюнкт-профессор призывал Верещагина не гнаться за внешним изяществом, на чем постоянно настаивал Марков, а следовать жизненной правде. А для этого надо было расширять свои наблюдения окружающего мира, подмечать характерные типажи, рисовать и писать с натуры. Настоящий художник не может быть домоседом, замкнувшимся в четырех стенах своего жилища и студии. Он — бродяга, странствующий по свету с мольбертом, собирающий живые впечатления и образы, накапливающий их в рисунках и этюдах.
Следуя добрым наставлениям Бейдемана, Верещагин упорно учился, рисовал с натуры, все чаще и чаще выходил с альбомом и карандашом на улицу для зарисовок с натуры. Начальный класс гипсовых фигур он закончил успешно, выполнив в качестве экзаменационного рисунка «Торс Геркулеса», и перешел в высший, натурный класс.
Между учителем и учеником сложились добрые, дружеские отношения. Александр Егорович помогал Верещагину не только в выработке уверенного и самостоятельного творческого почерка художника, но и в расширении общего кругозора. Но все же и Бейдеман при всей независимости своих суждений далеко не всегда мог переступить рамки схоластических программ и полностью отрешиться в своей педагогической практике от академических канонов. Чувство неудовлетворенности академической системой не покидало Верещагина. Это понимал и Александр Егорович.