На беду Верещагина, его первым наставником в академии стал тот же Марков. Впоследствии Василий Васильевич писал, вспоминая академические годы: «Профессора… почти все… были плохи… Виллевальде, Басин, Марков, Уткин, который от старости певал песни в классе, вельможа Бруни — всё это были чиновники, а не учителя»[30]. Но благодаря заботам Ф. Ф. Львова к формированию художественных навыков у подававшего большие надежды ученика подключился живописец совсем иного склада — Александр Егорович Бейдеман. Он сам лишь совсем недавно, в сентябре 1860 года, получил звание «академика по живописи исторической и портретной». Заметим, что тем же постановлением Императорской Санкт-Петербургской академии художеств Тарас Григорьевич Шевченко был признан «академиком по гравированию». В начале 1861 года Бейдемана назначили адъюнкт-профессором Академии художеств. Александр Егорович являлся бесспорно талантливым и весьма прогрессивным по взглядам на искусство человеком. Среди его близких друзей и сподвижников были блистательный мастер жанровой живописи Павел Федотов, известный иллюстратор «Мертвых душ» Александр Агин, художники Лев Жемчужников и Лев Лагорио. Совместно с двумя последними Бейдеман создал портрет мифологического «директора пробирной палаты» Козьмы Пруткова — популярнейшего «автора» изречений на все случаи жизни, который был плодом коллективного творчества поэтов — братьев Алексея, Владимира и Александра Жемчужниковых и их кузена А. К. Толстого. Как и Лев Жемчужников, Бейдеман придерживался демократических убеждений. Однажды, проживая вместе в Париже, они на пару исполнили обложку для газеты, печатавшейся Герценом в Лондоне в Вольной русской типографии, — рисунок колокола, звонящего на всю Европу и пробуждающего от апатии Россию. Эскиз послали Герцену, за что удостоились его благодарности. Что ни говори, поступок по тем временам смелый: стань он известен властям, мог бы привести к краху и карьеры, и всех жизненных планов.
Л. М. Жемчужников в своих «Воспоминаниях» посвятил А. Е. Бейдеману немало взволнованных строк и с глубоким сожалением писал, что из-за трагической случайности, прервавшей жизнь его коллеги[31], «этот громадный и разнообразный талант» не смог реализовать всё, на что был способен. Бейдеман, по словам Жемчужникова, был «одарен глубокой душой, умом, громадным воображением и художественной памятью» и настолько владел техникой, «что мог свободно высказать то, что хотел и чувствовал».
И вот А. Е. Бейдеман начал в стенах академии заниматься с Верещагиным. Василий Васильевич вполне оценил все его достоинства — как человека, художника и воспитателя. Позднее, завоевав российскую и европейскую славу, он неоднократно отмечал заслуги именно этого наставника в своем художественном развитии, подчеркивая, что Бейдеман повернул его «от сухого академизма к живой действительности». «Со времени знакомства с Бейдеманом, — вспоминал Верещагин, — я очень много рисовал на улице и прямо с натуры, и еще более на память всё виденное и замеченное; как тут не опошлеть в моих глазах академическому псевдоклассицизму»[32].
Зимой 1860/61 года Бейдеман привлек Верещагина к выполнению рисунков и гравюр для издаваемого Львом Жемчужниковым альбома «Живописная Украина». Обращение к «малороссийской» жизни не было для Жемчужникова случайным. Выходец из знатной дворянской семьи (по материнской линии братья Жемчужниковы были потомками графа Кирилла Григорьевича Разумовского), проживая летом в имении Разумовских, увлекся бытом, песнями и музыкой Малороссии. Его женой стала украинская девушка, бывшая крепостная. Отдельная глава в мемуарах Жемчужникова посвящена истории ее похищения у хозяев, враждебно отнесшихся к ее роману с родовитым дворянином.
К той же зиме, когда с Жемчужниковым начал работать Верещагин, относится личное знакомство Льва Михайловича с высоко ценимым им Тарасом Шевченко. После продолжительного разговора с Жемчужниковым Кобзарь записал в дневнике: «Как я счастлив был видеть человека, который искренне, нелицемерно полюбил мой родной язык и мою прекрасную бедную родину». Заметим, что и свой альбом Жемчужников начал публиковать как своего рода продолжение одноименного альбома Шевченко. По просьбе Жемчужникова рисунки и гравюры для его издания выполнили художники А. Е. Бейдеман, И. И. Соколов, К. А. Трутовский и др. Таким образом, Верещагин оказался в компании опытных мастеров, и в это время он под руководством Бейдемана овладевал техникой гравирования. В мемуарах Жемчужников писал, что и сам он усиленно гравировал в своей квартире на 11-й линии Васильевского острова, где его неоднократно посещал историк Н. И. Костомаров. В те же дни заходил и Верещагин, «который возбуждал к себе участие как во мне, так и в учителе своем, моем друге А. Е. Бейдемане. Этот гардемарин впоследствии сделался художником большой величины…».