How to fix two-factor authentication issues?

Recently I had to restore my iPhone to have the screen repaired. During that time, Apple has implemented automatic 2-factor authentication. I have discovered that my iTunes ID is affiliated with a phone number that has never belonged to me (from the last 2 digits it shows you when you try to put your account into recovery mode). Now, I cannot re-install or use any of my apps and I can barely make a call or send a text because the sign-in box pops up almost constantly. I have spoken to 5 Apple technicians who all think they can help and wind up telling me that not my billing credit card info, email verification, or my first born child will get me into my account or allow me to put it in recovery mode, only a phone number (which was probably a friend's or something that I used when I set it up 12 years ago to make iTunes purchases). I am absolutely baffled that there is NO solution. I was advised to create a new iTunes ID and bid farewell to my 12 years of purchases made across various generations of computers, MacBooks, iPods, iPads and now iPhones. FINE.

So I thought if it means I can use my apps or even get the **** pop up to go away I will, however when I tried to sign in to a different account the phone will not let me. It won't allow me to sign out of the account I was trying to get into (presumably because of the pop up). Additionally, I cannot sign out of find my iPhone to restore the phone and try to set it up with the new account. SO basically my phone has been rendered useless and Apple has essentially told me "tough luck". I cannot believe I can't verify my account another way, or that I have been spending this many weeks just trying to get my phone set up. Can anyone help?