I've dealt with deep-rooted issues on my iCloud account, and I have been asked by Senior Advisors (in the US) for permission to put my account into Troubleshooting mode, which requires that they provide you with a temporary password so they can access your account and see what's going on with it.
Talking with various Senior Advisors over the course of a few weeks that my account was in Troubleshooting mode, everyone knew what I was referring to, including the Corporate Executive Relations Office. This is definitely not a scam, although you are were right to be suspicious. This is a step you should only accept if you are comfortable with granting Apple Support full access to your iCloud account. This is normally a last resort for Apple Support.
If you have two-step or two-factor authentication on your account, an Apple Diagnostics device should appear in the list of Trusted Devices shortly thereafter.
Point of interest: the second or third time I've had to have my account put into Troubleshooting mode, I asked if I could simply hand them my password (it was already a temporary password, but due to a screwup on their part, my account was out of Troubleshooting mode). The Senior Advisor declined, citing policy that they must provide a randomly-generated password and could not accept a password from a customer. This is a very important point, because I get the impression from the reactions/answers that people think the support technician is asking @Oleg for his password. That is NOT the case.
I feel I should also add that yes, I am 100% certain I was talking to Apple employees the entire time. I contacted them through the Apple Support site, they called me back from the same Apple number every time, which I have saved in my Contacts, and every technician I was in touch with emailed me from an @apple.com address, to which I was able to send emails and get responses from (so that takes care of spoofed headers). They're able to Screen Share just by knowing your Apple ID but not your IP address, then ask you to upload diagnostics data to green header address ending in apple.com. It would take a very high degree of sophistication to pull off a scam of this magnitude (not to mention, if all they cared about was accessing your iCloud account, they could just stop once they got your password instead of spending hours upon hours going through troubleshooting steps that don't get them any additional data about you).
And obviously, when you get a response from the Corporate Executive Relations Office after emailing Tim Cook directly, you're pretty confident it's an Apple employee talking to you (the response includes your original email). If that person acknowledges that your account is in Troubleshooting mode and understands that you would like to get it out of it, then you're also pretty confident that Troubleshooting mode is a real thing.
I am in no way defending Apple's tech support procedures, just saying that yes, when all else fails, the company does ask to set a temporary password on your account. This allows the engineers to go in and troubleshoot themselves. This is definitely a legitimate scenario.