Can Android app run without being launched at least once? As much as I know, most apps won't ever start, unless you launch them at least once (even if they have a background service).

But what about those, that for example, have the Receive Intent Boot Successfull in their Manifest? Will that be enough to launch their code?
Yes, Android apps can start background services after system boot or intent received.
There are xposed modules (like defim's Boot manager or Receiver stop) that can prevent this behavior.