That's exactly what happened to me just a few days ago. I got an email alerting me that a secondary Google account of mine had been accessed, password changed, secondary email changed and I think even some kind of security question also changed (I don't even remember Google having those). Ok, no problem, I'll just tell Google I own it for whatever means they ask and change the password back.
Recovery email doesn't exist anymore. There's no phone number attached (I haven't accessed the account since before I had my first smartphone). And the account must be like 12 years old or so, there's no possible human way to remember the precise month I created it (I don't even remember the year).
I have all my Google accounts connected through gmail, and I can even receive the emails that go to that account, since they go to my main account. I tried for a full whole work day to get the account back, but there's just isn't any human I can talk to, so the account now belong to some russian hacker or who knows. Luckily for me is not a very important account and I haven't found anything important attached to it, but it's very scary.