AS you have specified in your question that you dont have access to your recovery mail and i believe you have tried everything to recover that id but you have failed to do so.
first create a new email id and apple id associated with it, # DONT FORGET THE PASSWORD THIS TIME###
Now you have only option to contact apple customer care on phone. I believe you have the original bill and box of the phone. Tell them your prob
Apple care executive on phone will ask you about every information about the purchase of the device. Then they will ask foryour new id, and will send you a link.
on that link you have to upload picture of your device bill.
Then relax for a week , apple will verify that the device is not the stolen one and will verify the purchase detail. After few days if everything went well lets hope fot that then you will receive a mail from apple team that the device has been removed from the previous id and now you can use it with your new id.