The difference between STICKY and NON_STICKY services is that STICKY services are restarted after being killed. I don't think it's possible to guarantee that your service will never be restarted - if memory is low it might be restarted.
If you need to preserve the state, you can save variables in a database. To see if the service is being created for the first time or restarted, you can check if the intent in onStartCommand is null.
If you only need to preserve the initial state when the service was created, you can use START_REDELIVER_INTENT which will resend the Intent used to create the service in onStartCommand.