I'm attaching a proof of concept code for a ScheduledExecutor
interface, and a ScheduledThreadPoolExecutor implementation
(unfortunately I can't upload it as a mercurial diff for now).

Here's what the API looks like:

"""
from concurrent.futures import ScheduledThreadPoolExecutor
import time

def say(text):
    print("{}: {}".format(time.ctime(), text))

with ScheduledThreadPoolExecutor(5) as p:
    p.schedule(1, say, 'hello 1')
    f = p.schedule_fixed_rate(0, 2, say, 'hello 2')
    p.schedule_fixed_delay(0, 3, say, 'hello 3')
    time.sleep(6)
    say("cancelling: %s" % f)
    f.cancel()
    time.sleep(10)
    say("shutting down")
"""

schedule() is for one-shot, schedule_fixed_rate() for fixed rate
scheduling (i.e. there will be no drift due to the task execution
time), and schedule_fixed_delay() is for fixed delay (i.e. there will
always be a fixed amount of time between two invokations).

Random notes:
- the scheduling is handled by a new SchedQueue in the queue module:
sched would have been useful, but actually it can't be used here: it
stops as soon as the queue is empty, when it calls the wait function
it won't wake up if a new task is enqueued, etc. Also, I guess such a
queue could be useful in general.
- I had to create a DelayedFuture subclass, which is returned by
schedule_XXX methods. The main differences with raw Future are that it
has a scheduled time and period attributes, and supports
reinitialization (a future can only be run once). It can be cancelled,
and also supports result/exception retrieval.
- I don't know if a process-based counterpart
(ScheduledProcessPoolExecutor) is really useful. I didn't look at it
for now.