Буквально за несколько месяцев Матюшенко насмерть переругался и со всеми видными революционерами. На Горького, к примеру, он обозлился, увидев того ехавшего по улице на автомобиле, а социалиста Жореса он едва не отлупил прямо на митинге. Как пишет эсерка-террористка Ивановская, в 1907 году видевшая Матюшенко в Женеве, тот был разочарован тем, что лидеры революционеров, находящиеся в эмиграции, вершат судьбы тех, кто непосредственно участвует в революции в России. Под революцией он понимал исключительно грабежи банков и убийство интеллигентов и офицеров. Чтение трудов Маркса он объявил глупым и ненужным делом, уделом все тех же «очкастых интеллигентов». Уделом же настоящих революционеров, по его мнению, должны были быть револьвер и бомба. От Талона Матюшенко, к примеру, хотел получить деньги на организацию матросского отряда «смерти», который должен был пробраться в Петербург и устроить там всем беспощадный террор. Гапон деньги обещал, но так их и не дал, потому как сам был повешен за измену соратниками-эсерами.
Любопытно, что Матюшенко вместе с Талоном планировал организовать некий поход вооруженного отряда матросов-потемкинцев в Россию, чтобы начать новую революцию. Но против этой безумной идеи выступил куда более популярный среди команды машинный квартирмейстер Степан Денисенко, и затея провалилась.
Известный эсер-террорист Б.В. Савинков якобы лично предлагал Матюшенко стать профессиональным эсером-террористом. Тот был в принципе не против, но ему не понравились аристократизм и интеллигентность Савинкова. Так и не договорившись, две революционные знаменитости расстались.
Одни считали Матюшенко социал-демократом, другие — эсером, третьи — анархистом. Сам он о себе говорил так: «Я не признаю никаких партий, для меня хороши все, кто бьет это правительство, и кто его сильнее бьет, те для меня лучше». Это высказывание Матюшенко я приводил уже выше, но в данном случае оно, думается, характеризует уже не столько общее отношение к партиям потемкинцев, а личное отношение к партийным функционерам самого Матюшенко.
В воспоминаниях революционеров-эмигрантов, встречавшихся с Матюшенко, они единодушно описывают его как крайне неумного, хамоватого авантюриста, патологически любившего рассказывать о своих убийствах. Немудрено, что от него практически все отшатнулись. В эмигрантской среде Матюшенко быстро становится одиозной личностью, всякий интерес к нему пропадает. В 1907 году Матюшенко опубликовал в журнале «Буревестник» статью «Своим бывшим учителям». Этот документ интересен как исповедь человека, пришедшего к крайним антиинтеллигентским выводам Короче говоря, в статье Матюшенко открыто призвал вешать всех умников-интеллигентов, от монархистов до социалистов.
Встречаясь с руководителями революционных партий, Матюшенко явно ищет покровителей и быстро их находит. Во время своего пребывания в Швейцарии, а затем и в Нью-Йорке, Матюшенко существует исключительно за счет еврейской «демократической» эмиграции. Особенно же теплые отношения сложились у него в это время с Азефом Из воспоминаний «потемкинца» Денисенко: «С Матюшенко я снова встретился в Нью-Йорке. Когда я приехал в Монреаль, я застал там письмо от него, в котором он писал мне; “Ну, чего застрял там? Приезжай в Нью-Йорк — будем делать революцию и бить «социалистов»!” Я отправился туда и нашел, что, действительно, бить их нужно было, за исключением доктора Каплана, Зиновьева и Каца…» Но в США «делать революцию и бить социалистов» Матюшенко не дали и быстро его оттуда попросили.
После долгих метаний по всем партиям Матюшенко в конце концов примкнул к «Южнорусской группе анархистов-синдикалистов» Новомирского, сторонника антиинтеллигентской линии в анархизме. Группа Новомирского была, по существу, самой настоящей бандой, давно вышедшей из подчинения ЦК партии анархистов и промышлявшей на свой страх и риск убийствами и эксами. Это были как раз люди, наиболее близкие Матюшенко по духу. С «новомирцами» он нелегально переправляется в Россию «делать новую революцию».
Последующая судьба Матюшенко была, впрочем, печальной. Такие одиозные личности не могли долго жить. Матюшенко должен был повторить судьбу лейтенанта Шмидта и попа Гапона, Первого убили враги, а второго — соратники. Матюшенко повторил судьбу сразу обоих. С главным «потемкинцем» был разыгран средний вариант: его сдали врагам свои же соратники. Вскоре по заданию эсеров он вернулся в Россию, чтобы организовать ряд террористических актов в южных губерниях. В июне 1907 года он возвратился в Россию под чужой фамилией, но был схвачен в Николаеве, как член группы анархистов-синдикалистов, и опознан одним из филеров. Затем арестованного Матюшенко опознал на очной ставке и бывший мичман с «Потемкина» Бахтин, ставший к этому времени уже лейтенантом. Это был тот самый Бахтин, которого в день мятежа Матюшенко лично избивал прикладом.
20 октября 1907 года по приговору военно-морского суда Матюшенко был повешен во внутреннем дворе севастопольской тюрьмы.