Короче говоря, компания своим составом и своей типажностью напоминает троицу (плюс девушка) из «Заставы Ильича». В «Верзилах» образ Володи — как и образ Сергея в «Заставе…» — имел автобиографические черты: Володя был сиротой и воспитанником Суворовского училища. Теперь Шпаликов эти черты убрал: автобиографизм непременно вёл бы к тому, что герой стал бы сильно выделяться рядом с другими, а «задвигать» на второй план Кольку с Сашей автору, наверное, не хотелось.
На главные роли в картине были нужны молодые актёры. На роль Володи Ермакова Данелия пригласил актёра Алексея Локтева, недавно окончившего ГИТИС и теперь работавшего в Московском театре им. Пушкина. Роль сразу принесла ему известность, но дальнейшая актёрская судьба Локтева сложится трудно и противоречиво. Сниматься он будет немного, всё больше в ролях второго плана. Ролей, равных сыгранной им у Данелии, у него уже не появится. Позже он переедет в Ленинград, затем вернётся в Москву, будет пробовать себя в драматургии, в какой-то момент уйдёт в религию, станет прислуживать в храме в подмосковных Мытищах. Погибнет в 2006 году в автокатастрофе в Благовещенске во время кинофестиваля «Амурская осень», оставив ощущение неполной реализованности таланта. Так получилось, что образ Володи Ермакова остался главным памятником актёру Алексею Локтеву.
На роль Кольки Шпаликов предложил режиссёру восемнадцатилетнего Никиту Михалкова, будущую знаменитость. В то лето Никита только собирался поступать в Щукинское театральное училище. Михалков вполне может считать Шпаликова своим крёстным отцом в кинематографе. Гена, как мы помним, дружил со старшим братом Никиты, Андреем, был вхож в дом Михалковых. Вот и юный Никита ему приглянулся. Претендент на роль поначалу показался Данелии совсем уж «маленьким», но Никита быстро «подрос» — втянулся в работу и вскоре осмелел настолько, что самонадеянно затребовал (как потом выяснилось, с подсказки брата) повысить оплату своего съёмочного дня с восьми рублей до двадцати пяти. Мол, съёмки уже идут, часть материала отснята, никуда не денутся, заплатят. В то время и восемь рублей были суммой очень неплохой, особенно для начинающего, а уж двадцать пять… Такую ставку получали самые знаменитые актёры. Но коса нашла на камень: Данелия оказался человеком стойким и дал понять, что будет пробовать другого актёра. Да если бы даже он и поддался Михалкову — надо представлять неповоротливую советскую бюрократическую систему, чтобы понять, какой волокитой — скорее всего, безрезультатной, и уж точно затяжной — это могло бы обернуться. В общем, пришлось Никите пока «довольствоваться малым», большие гонорары ожидали его, будущего автора «Утомлённых солнцем» и «Сибирского цирюльника», впереди. В фильме «Я шагаю по Москве» он обаятелен своей непосредственностью и разговорчивостью. Это его герой обыгрывает «пушкинскую» тему, прозвучавшую в шпаликовской песенке о Пушкине и Вяземском. Отхлёбывая чай из чашки, он показывает Володе за окно и говорит: «А вот в том доме когда-то Пушкин жил» (в тексте «Верзил» в этом месте была прямая автоцитата: «Здесь когда-то Пушкин жил»). На вопрос Володи: «А теперь кто живёт?» — Колька не моргнув глазом отвечает: «Родственники». И даже показывает гостю одного из них — якобы пушкинского «правнука», который «края (то есть крайнего на футбольном поле игрока. — А. К.) играет в „Торпедо“». На Колькин свист в окне напротив появляется темноволосый кучерявый парень, у которого, оказывается, нога не в порядке: врачи «мениск подозревают». «Похож» (в смысле: на Пушкина), — говорит Володя. Типично шпаликовская шутка, включая «мениск». Здесь чувствуется своеобразный автобиографизм: мы помним, что сам автор сценария повредил в военном училище колено.