You can offer to let users log in with Facebook Connect and Google Accounts, etc. If I'm going to try out a new service, I'd rather use one of my existing log-ins than trust a brand new start-up to store my information securely. It's not their core competency.
Can you not just use a password manager and generate unique credentials for the new service, and give them a unique e-mail address as well if you're worried about spam?
Or are you worried about whatever data you put on the service after you've logged in?
