Linux: разрешение на удаление файлов, но запрет на создание
Разместить эту директорию на отдельном разделе. Запустить простенький демон, который будет заполнять все освободившееся место в этой директории (на директорию налепить t-бит, файлу назначить владельцем рута).
Все. Задача решена: при удалении пользователем файла место сразу же будет забито, новый файл он создать не сможет.

А невелосипедных способов, естественно, не существует.
Нельзя.
Удаление и создание — это запись в директорию.
Право на запись либо есть, либо нет.