Народився у Ставрополі. Навчався у місцевому футбольному інтернаті «УОР-Динамо» (Ставрополь), професійним футболістом не став, через травму змушений був у 20 років розпочинати тренерську кар'єру. Має ліцензію PRO-UEFA[1]. Працювати розпочав 1992 року у ставропольській ДЮСШ №4 як помічник тренера, одночасно навчався в інституті. У 1996-2000 роках був тренером у футбольному інтернаті ставропольського «Динамо». У 2000-2002 тренував збірну футболістів СДУ. У 2002 році запрошений до московської ДЮСШ ЦСКА, де пропрацював рік. 2005 року, закінчивши Вищу школу тренерів, почав працювати в дублі раменського «Сатурна».
Після завершення сезону 2008 року запрошений своїм старим знайомим Геннадієм Бондаруком до «Жемчужини-Сочі»[2]. У сезоні 2009 року став найкращим тренером другого дивізіону та вивів «Жемчужину» до першого дивізіону. Однак після низки невдалих матчів у сезоні 2010 року звільнений з посади головного тренера і обіймав посаду старшого тренера команди[3]. 27 вересня 2010 року знову заявлений як головний тренер. 14 грудня 2010 року призначений головним тренером мінського «Динамо», але за підсумками першого кола чемпіонату усунутий із займаної посади за незадовільні результати. У 2011 році очолював молодіжну команду ФК «Краснодар» та входив до тренерського штабу головної команди. 12 січня 2012 року Василенку запропонували попрацювати в «Анжи» на посаді старшого тренера клубу.
У 2013 році був головним тренером «Уралу». У листопаді 2013 року після нічиєї з «Крилами Рад» контракт було розірвано.
У 2014 році працював головним тренером у ФК «Сочі»[5], але після серії з невдалих матчів покинув клуб[6].
У 2016—2018 роках тренував латвійський РФШ[7] та литовський «Тракай»[8], з останнім з вище вказаних клубів пройшов два кваліфікаційні раунди в Лізі Європи 2017/18, але був звільнений за незадовільні результати у чемпіонаті Литви.
У червні 2018 велися переговори з воронезьким «Факелом» про призначення на посаду головного тренера[9]. З вересня по грудень 2018 року був помічником Ігоря Ледяхова в калінінградській «Балтиці»»[10][11]. З червня 2019 року – старший тренер у курському «Авангарді». У вересні 2019 року напередодні 14-го туру Першості ФНЛ-2019/20 призначений головним тренером команди[12], але в грудні залишив клуб[13].
У лютому 2020 року призначений головним тренером «Мордовії»[14]. Залишив клуб у серпні 2020 року у зв'язку з його розформуванням.
У вересні 2020 року став головним тренером воронезького «Факела», який знаходився в зоні вильоту ФНЛ на 17-му місці[15]. Під керівництвом Олега «Факел» за підсумками сезону-2020/21 посів 9-е місце, у сезоні-2021/22 вийшов у Прем'єр-лігу. Залишив посаду головного тренера 6 вересня 2022 року, після восьми турів чемпіонату РПЛ[16].
22 березня 2023 року очолив «Аланію», з якою підписав контракт на півтора роки з опцією продовження ще на один рік[17]. 22 листопада 2023 року контракт було розірвано. За словами президента клубу Володимира Гурієва, основним чинником стали останні результати команди, які не тішили ні вболівальників, ні його. Усього під керівництвом Василенка «Аланія» провела 31 матч: 14 перемог, 11 нічиїх та 6 поразок[18]. 16 січня 2024 року став головним тренером грузинського клубу «Телаві».
28 серпня 2024 року очолив новоросійський «Чорноморець», з яким підписав контракт на 2 роки з можливістю продовження ще на 1 рік.
