Ship the keys with the device on a sheet of paper. Generate them on first boot, display them and strongly encourage users to print and save them. Provide keys t

Ship the keys with the device on a sheet of paper. Generate them on first boot, display them and strongly encourage users to print and save them. Provide keys to the user on request after a reasonable identity verification. Have the user provide an emergency fallback password on device registration. Hire a skywriter to draw random characters and give the user a particular time to start and stop recording. Mail a hardcopy of the keys to the user. Encode the keys as a subliminal message that your device plays to you in Steve Jobs' voice while you sleep. Really, literally any other option than "never give the user keys".