На каком-нибудь другом основании. :)
На основании п.5 ст.40 КЗоТ в вашем случае - нельзя.

Можно ещё попробовать по п. 2 ст. 40, но для этого нужно заключение врачей, что сотрудник не может выполнять свои обязанности по состоянию здоровья.

По поводу оснований увольнения по инициативе собственника или уполномоченного им органа в соответствии с п. 2 ст. 40 КЗоТа, могу привести Письмо Министерства труда и соцполитики Украины от 01.06.99 г. № 06/2-4/1, оно правда старенькое, но является действующим:
"Повідомляємо, що п. 2 ст. 40 КЗпП України передбачає звільнення працівника внаслідок неналежного виконання ним своїх обов'язків з причин, які не залежать від працівника і тому не можуть бути поставлені йому в вину. Цими причинами можуть бути недостатня кваліфікація або стан здоров'я працівника.
Кожна з цих причин як підстава для звільнення повинна бути настільки серйозною, щоб саме вона перешкоджала працівникові належним чином виконувати покладені на нього трудові обов'язки. Невідповідність працівника займаній посаді або виконуваній роботі має бути доведена власником або уповноваженим ним органом, оскільки саме власник є ініціатором звільнення.
Невідповідність займаній посаді або виконуваній роботі внаслідок недостатньої кваліфікації може бути підставою для звільнення даного працівника лише тоді, коли власник має фактичні докази того, що саме через це працівник не може належним чином виконувати покладені на нього трудові обов'язки, і коли такого працівника неможливо, за його згодою, перевести на іншу роботу. Невідповідність займаній посаді або виконуваній роботі внаслідок недостатньої кваліфікації може бути визнана за результатами атестації працівника".
В связи с изложенным, могу предположить, что фактическими доказательствами того, что именно из-за состояния здоровья работник не может надлежащим образом исполнять возложенные на него трудовые обязанности, не обязательно должно являтся медицинское заключение.
Возможно во время болезней данного работника по причине не надлежащего исполнения им своих трудовых обязанностей, к примеру, предприятию был приченен определенный вред (нанесены убытки), что может быть подтверждено соответствующими документами; или пострадала трудовая деятельность других работников в плане отсутствия возможности выполнять свою работу (часть работы) как следствие невыполнения своих обязанностей болеющим сотрудником, в результате чего вцелом работа была не выполнена должным образом или в нужные сроки, в рез-те чего опять же таки пострадали интересы предприятия и т.п. следствия.
Тогда нужно будет собрать документальные подтверждения и приложив к ним больничные листы, определить таким образом предметно-временную зависимость ненадлежащего исполнения своих трудовых обязательств данным работником от его состояния здоровья.
Хочу также заметить, что в жизни бывают обстоятельства, которые происходят не по воле самого человека и в таких случаях нужно уметь проявлять не властную хладность ума, удовлетворяя амбиции относительно своей материальной выгоды, а элементарное уважение и гуманизм к людям с которыми мы работаем.
Естественно, случаи и люди бывают разные, поэтому опытный руководитель всегда должен разобраться в ситуации и понять кто есть кто.
Всем желаю удачи :)

И как поступили?

Эти все вопросы четко регламентированы Инструкцией по ведению ТК:

2.20-1. Трудові книжки працівників, які працюють на умовах трудового договору у фізичних осіб - суб'єктів підприємницької діяльності без створення юридичної особи з правом найму, та фізичних осіб, які використовують найману працю, пов'язану з наданням послуг (кухарі, няньки, водії тощо), зберігаються безпосередньо у працівників.

Зазначені в абзаці першому цього пункту фізичні особи роблять записи до трудових книжок працівників про прийняття на роботу та звільнення з роботи відповідно до укладених з працівниками письмових трудових договорів, що зареєстровані в установленому порядку в державній службі зайнятості. Під час прийняття на роботу вноситься запис: "Прийнятий на роботу (далі зазначається професійна характеристика робіт) за трудовим договором (зазначаються дата та номер договору), зареєстрованим у державній службі зайнятості (зазначається повна назва центру зайнятості)", при цьому у графі 4 зазначається, на підставі чого внесено запис (дата і номер реєстрації трудового договору державною службою зайнятості: "трудовий договір (номер), зареєстрований (дата)"), а при звільненні - запис: "Звільнений з роботи (далі зазначається підстава звільнення з посиланням на відповідні статті КЗпП України)", при цьому у графі 4 зазначається дата зняття трудового договору з реєстрації державною службою зайнятості: "трудовий договір (номер) знято з реєстрації (дата)".
Унесені фізичною особою до трудових книжок записи підтверджуються підписом посадової особи органу державної служби зайнятості, який зареєстрував трудовий договір, і засвідчуються його печаткою.
Если ТД есть, то необходимо спросить у работника (ведь книжка хранилась у него ) почему в ней нет необходимых записей и печати ЦЗ при увольнении? Ведь договор на бумаге есть, значит заключался, а где в этот момент была его ТК?.

Увольнение
 

Помогите! Как уволить работника, который не выполняет свои обязанности и отказывается увольняться по собственному желанию?

П. 3 ст. 40 КЗпП У.
Але це ви зможете зробити тільки у тому випадку, якщо у вас діють на підприємстві і доведені до працівників Посадові інструкції і Правила внутріщнього трудового розпорядку.

Спасибо большое :)

Подскажите, как правильно оформить его увольнение. Нужно ли составлять какие-либо записки или акты? И т.д.

Ну а як же!
Звільнення за цією підставою - це вид дисциплінарного стягнення. Тому порядок накладання - такий самий, як і при оголошенні догани.

Зауваження: звільнити можна тільки при ситстематичному невиконанні своїх обов'зків і при умові, якщо до цього працівника вже застосовувались інші дисциплінарні стягнення (догани).

І ще: застосувати дисциплінарне стягнення можно тільки за якесь конкретне порушення (наприклад, невчасно здав звіт, не виготовив деталь...), а не за невиконання своїх обов'язків "взагалі".