Родился 16 марта 1921 года в городе Беловодске (ныне Старобельского района Луганской Народной Республики). В 1938 году окончил 9 классов средней школы № 9 города Майкопа (ныне столица Республики Адыгея) и Майкопский аэроклуб. С 26 февраля 1939 года в рядах Красной Армии, призван Майкопским ГВК. В апреле 1940 года окончил Качинскую военную авиационную школу пилотов. Служил младшим лётчиком в 92-м ИАП ВВС Киевского Особого военного округа.

С 22 июня 1941 года лейтенант Ф. С. Василенко в действующей армии: в должности пилота 92-го ИАП. По 27 сентября 1941 года воевал на Юго-Западном фронте (в составе 16-й САД), летал на И-153. В районе Киева полк попал в окружение, лётный состав перелетел из киевского "котла" в Харьков, а технический состав прорывался из окружения с боями в направлении Харькова. С 1 октября 1941 года полк находился в 11-м ЗИАП Северо-Кавказского военного округа (город Ростов-на-Дону), где проходил переформирование. С 15 октября 1941 года в 25-м ЗИАП Закавказского военного округа (город Аджи-Кабул, АзССР) и с 28 декабря 1941 года уже во 2-м ЗИАП Московского военного округа (станция Сейма, Горьковской области) переучивался на истребители ЛаГГ-3.

С 8 марте 1942 года приступил к боевой работе на Волховском фронте (в составе авиагруппы генерал-лейтенанта А. А. Новикова, с 30 марта - уже 1-й Ударной авиагруппы Резерва СВГК), в должности командира звена. С 15 апреля 1942 года боевой работы не вёл: полк проходил доукомплектование в резерве ВВС Волховского фронта (станция Яхново, Ленинградской области), а с 18 мая 1942 года возобновил боевую работу на Волховском фронте.

К лету 1942 года лейтенант Ф. С. Василенко был уже заместителем командира эскадрильи. В начале июля 1942 года представлялся к званию Героя Советского Союза, но не получил его (награждён орденом Отечественной войны 1-й степени). Согласно данных наградного листа, к тому времени он совершил 320 боевых вылетов (из них 78 - на штурмовку), провёл 123 воздушных боя, сбил лично и в составе группы 16 самолётов противника.

16 июля 1942 года заместитель командира эскадрильи 92-го истребительного авиационного полка (1-я Ударная авиационная группа Резерва Ставки ВГК, ВВС Волховского фронта) лейтенант Ф. С. Василенко вылетел в район Будогощь (Ленинградской области), в условиях плохой видимости врезался в мост, разбил самолёт, а сам получил тяжёлые ушибы и перелом позвоночника. Был отправлен в госпиталь города Боровичи (Ленинградской области), где 25 июля 1942 года скончался от полученных ранений. Похоронен на городском кладбище, могила № 4426. Всего совершил более 320 боевых вылетов, провёл около 125 воздушных боёв, сбил лично 6 и в составе группы 10 самолётов противника.

Награждён орденами: Ленина (22.04.1942), Отечественной войны 1-й степени (05.12.1942).