Как уже написано в комментах, делать такое очень не рекомендуется, т.к. пользователи ожидают, что оператива будет очищена от приложения, когда они его убивают. Если же оно убивается системой, то тоже не просто так, а чтобы освободить ту же оперативу. Если перезапускать сервис или активити при этом, то памяти будет не хватать и какая-нибудь игруха тяжёлая у пользователя будет падать. Не надо так.
Если всё же хочется быть злым и вообще нехорошим, то пропишите старт сервиса в, например, onDestroy(). Не уверен, что сработает в этом месте startService(), а вот посылка своего сообщения своему ресиверу, стартующему сервис, через, например, LocalBroadcastManager наверняка сработает.
Или сделайте AlarmManager, коий будет каждый n минут/ секунд проверять, крутится ли сервис и, если нет, стартовать его.
Главное помнить, что это плохо-плохо-плохо.