Aprovecho este hilo para comentar dos cosas:
1. Se han publicado los vídeos de la DroidCon de San Francisco, y hay uno que habla sobre el tema de gestión de tiempo en Android:
2. He encontrado esta librería, y esta bastante bien parida en cuanto a crear Jobs y que el sistema decida cuando ejecutarlos:
https://github.com/evernote/android-job