How about using the Task Scheduler? In Windows 7, there's a "Security options" section where you can set an option for a task to run whether a user is logged on or not. You can specify an executable file, and it'll start when Windows starts up.
(This won't scale though, if you're looking for an option when a user installs your software. For that, a service is the correct way to go... you may need to elaborate in your question why exactly you can't use a service.)