I've kind of run into this problem before. I find for one time job scheduling, the "at" command had worked well for me.
Umm... Another approach might be to schedule a cron job to run a script every so often to see if a request for a cron job update has been made. If so, check what the request was and update crontab. Depending on your needs, maybe checking every hour or every 15 minutes might work. This requires a little creativity on your part.
Another idea I had involved socket servers and having one listen for new "job" requests and then have the socket server update crontab. But I have a feeling you open up another can of worms with this approach if you're not careful.