Apple ID ask for a recovery email, so if you entered that other email as part of security and setup, this is expected information to progress through the automated reset procedure.
Additionally, if someone else guessed or got your password, they may have changed things. If you're really stuck after thinking this through and reading carefully the steps and being sure you are doing all the steps - in the order asked from:
Then your next step would be to contact support to make sure you don't have any other avenues to reset the password. Hopefully there is another item you set up like security questions or a second authorization factor or telephone number.
Usually you don't lose all access to an Apple ID unless you lose or forget two different pieces of the information you entered. Most cases you get three different avenues for resetting a password.