Deprecating SMS authentication is a good thing, in all honesty. SMS is not a secure form of data transfer, and is trivially intercepted. You can buy and setup an illegal Stingray device relatively easily, and capture basically all wireless data from a phone within range.
That said, if the device was truly never used for 2FA, then there wouldn't be any push-based 2FA on the account to begin with. Unless there's another device that's been authenticated with your account somewhere, like an old phone. In which case, that's where your login requests are being pushed to. That's a setting that can only be enabled by successfully authenticating with a device at least once in the past.
If there was never any other authenticated device, then that setting on your account isn't there. Enabling that feature is a two-step process, and step 1 involves configuration on a local device before it can be enabled remotely on your account.