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