Собственно, надо как-то реализовать, чтобы скрипт, беря данные из MySQL на основе этих данных прописывал себя на регулярное выполнение в cron. Понятно, что можно реализовать через subprocess, но неужели нет более изящного решения?

Можно добавлять файлы самому /etc/cron.*/, но нужны рутовые права (по умолчанию в /etc/crontab все эти папки подключаются).
Для пользователя опредлены /var/spool/tabs и /var/cron/tabs.