How can I restore access to my iCloud account after too many attempts?

You are correct that if you set up a Recovery Key on your account, you will need either that key or a Trusted Device to gain access to your account. There is no other way and Apple does not keep a copy of that key. It is a terrible idea to save your Recovery Key on your phone or in iCloud, since the reason you will need to use the Recovery Key is that you have lost access to the service. You do mention that "my account recovery key was in the house", so are you able to find it? That would appear to be the only option. Apple specifically state this when you get your Recovery Key:

When you generate a recovery key, print a copy or write it down. Keep it in a safe place, so that you always have access to your Apple ID. You can give a copy of your recovery key to a family member, or keep copies in more than one place.

• Legal Route - The key that is provided to you encrypts the data so it is not available to anyone else. Since Apple does not have the key, there is no way for you to be able to force them to reveal it.
• Willing to Pay money - Unfortunately all you will find are scams that may claim they can do it, but you see that there are many places on the internet that will take your money without providing any results.

For your other question on your Verizon phone number, the only solution with be through Verizon if it is possible. Apple has no control over the numbers used by a cell provider.

Having a recovery key means you have elected to not let Apple have the ability to recover your account. It is more secure but has its downsides and is probably excessive for most people. I list your options below.

The information below is based on Apple's support article: Set up a recovery key for your Apple ID - Apple Support with quoted excerpts. Each section outlines the different situations and the strategies that may relate to use of a recovery key. If you are not familiar with trusted devices and numbers, see this support article —> Two-factor authentication for Apple ID - Apple Support

- If you still have access to your Apple ID and password but have lost your recovery key:

"You can generate a new recovery key from Settings or System Preferences on a trusted device." Refer to the steps in Set up a recovery key for your Apple ID - Apple Support about how to do this on different types of equipment (Apple equipment only).

- If you have forgotten your Apple ID password, have lost your recovery key, but still have access to a trusted device.

"you can try to regain access using your trusted device protected by a passcode." The process is outlined in this support article: If you forgot your Apple ID password - Apple Support This does not involve using a recovery key.

- If you have a forgotten password and you do not have access to a trusted device:

"you can use your recovery key, a trusted phone number, and an Apple device to reset your password."

- If you have lost your recovery key and have lost access to both your account and trusted items:

A recovery key is designed as an alternative to Account Recovery ( How to use account recovery when you can’t reset your Apple ID password - Apple Support ) which is where Apple helps you regain access to your account. However, "when you generate a recovery key, you can't use account recovery." You can try to contact Apple (see: Contact Apple for support and service - Apple Support ), but to me the previous statement implies that setting up a recovery key excludes Apple from being able to do anything. Apple says: "Using a recovery key is more secure, but it means that you’re responsible for maintaining access to your trusted devices and your recovery key. If you lose both of these items, you could be locked out of your account permanently."