You use some other form of authentication, like a password, or clicking an emailed link, or clicking an "approve" button on the old device if available, or anything else that makes sense for your relationship with your users.
And how does the server remember that you've provided one of those other forms of authentication? Recall that the original goal was to be an alternative to cookies...
