Lots of systems email users an initial password which must be changed at first login. It's not the world's most elegant solution, but it's also not terrible and basically does an implicit email verification. I'm not sure that it's any worse than sending a URL with an embedded token that takes the user to a password-change page.
