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