Wenn ich meinen verlinkten Stackoverflow Artikel richtig verstehe, ist ein Dienst keine Voraussetzung. Jede beliebige Activity kann man um einen BroadcastReceiver erweitern, damit ist auch eine reguläre App - Activity "autostartbar".
Ich hatte Mitte das Jahres mal recherchiert und da bin ich auf die oben verlinkte Info gestoßen. Dort musste man einiges in den "Untiefen" von Android/Java ändern. Das wollte ich mir nicht antun.
Ich werde mir deinen verlinkten Artikel nochmals genauer anschauen. Vielleicht reicht auch dieses.