Con móvil rooteado, tasker es una buena opción, correrá una vez cargado android según las reglas que le indiques.
La otra es habilitar el directorio init.d del móvil (requieres un kernel que lo soporte) e incluir un script en init.d para iniciar la app. El directorio init.d se ejecuta primero al encender el móvil.
Más información de tasker e init.d la puedes consultar buscando en google ó en este foro.