1. User enters email
2. We send a verification code to their email
3. User enters code, is signed in "indefinitely" (very, very long cookie)
Whether or not they had an account before hand is irrelevant, we just register a new account if the email is new. The occasional user has multiple emails and sometimes creates a new account accidentally. This is an acceptable disadvantage as we've observed dramatic improvements in registration and sign in conversions.
There is some risk analysis to do here on the code lifetime and cardinality (better yet, use a lockout mechanism.) If your service isn't particularly important, I recommend this strategy.
Mail on iOS now supports this type of mechanism too (same as the Messages one-time code functionality) so it can be quite painless for some users as well.