There are several ways how you could establish that. Though, as you discovered, most really good solutions require your device to be rooted, there are some methods working even without root:
Autorun Manager you've already mentioned -- to my experience, this is the best app in this area. This app also offers a non-root mode you might want to give a try. But like other apps in non-root mode, it can only kill apps after they've started -- while in rooted mode, it can disable the corresponding "Listeners" and thus keeping the app from being started at all. Even if killed right away, many of those apps simply re-start again (which is detected by ARM, and that app then left alone to avoid a kill-start-kill cycle). Moreover, they can only handle the
boot_completed event -- but some apps (like e.g. Google Maps) start on so many different occasions (network changed, sdcard mounted...) -- where again the Pro-Version in root-mode can deal with, but the non-root mode can't.
If you've got Android 4.0 or higher, there might be another useful "work-around" -- at least if it's a rarely used app: Go to Settings→Apps→Manage Apps, scroll to the app in question, tap it once, and then tap the "Disable" button. App is gone (disabled) then, no longer shown in the app drawer -- and no longer started automatically or manually, as to the system it is "non existent". If you need it again later, go to the very same place, scroll to the very end of the list (Ah! there the disabled apps have gone to...), tap it again, and tap the "Enable" button -- back it is!
As this is a rather complicated way, it's probably not feasable for apps you need on a daily basis. But if it's an app you need no more often than once a month, it might be worth the effort.
Some related questions go deeper into details, many of them including stuff only relevant for rooted devices. However, they might be worth reading in this context, so I include their links with my answer here: