I've given this type of interview for quite a few companies. I hate to say it, but while there is some stuff you can probably finesse for your personal style, there are some unavoidable requirements to this type of interview.
The Goal
The goal here is not to have a finished and perfectly working piece of code from you. The goal here is to learn how you think & communicate while you attempt to write a basically decent bit of code. The idea here is the collaboration and that is part of the job. You are right that most coding exercises are reasonably fake, because it's hard to cook up a reasonably complicated sample problem that can also be reasonably likely to be solvable in an hour and not have that be rather fake. But the case of having a hard problem that takes a bit of discussion prior to being completed is something the software engineers on the teams I run face every day, and it's not unusual in some companies to do pair programming where you are literally writing code in front of someone.
While not every company that runs this type of interview is a huge pair programming culture, most companies that run this interview do expect that the software engineers will work in teams that regularly communicate about hard problems while they are in the midst of solving them, and they regularly do it ad hoc with very little preparation. I've run incidents for both Akamai Technologies and AWS and it's been absolutely vital in those cases to be able to discuss half-baked & probably wrong software designs on the fly with little or no preparation.
The other anti-goal is (unfortunately) avoiding cheating. Hiring someone who can't actually do the job is an extremely expensive mistake, and it's worth loosing out on hiring some great engineers if it means avoiding the cost of hiring bad ones. Having you go offline and appear later with a solved problem can raise the question of whether you did the work yourself.
Some partial solutions:
That said, I too experience total brain-freeze when trying to solve problems in front of humans. Especially in the fake collaborative context of an interview, where I know I'm being judged. So here's some mitigations I would have no problem compromising on as both the interviewer and interviewee:
Have a whiteboard or work surface they can see - put a video camera on it. Because I do this day to day, I actually have a whiteboard desk surface and a camera pointing down. But in the early days, I had a piece of white printer paper which I held up to my laptop camera periodically and got the same effect.
Feel free to say "give me 5 min to collect my thoughts" - you may need to stay on camera, but you can ask for silence and even turn away from the camera. You can't go solve the problem for 20 minutes and come back with a finished result, but you can take that 5 min to calm down a sec, get a general idea of what you want to do, and then re-engage.
Most people that succeed in this sort of interview can start by pulling out a common pattern from a set of templates - stuff like what data structure they may use, or how they would iterate through inputs - are generally patterns that boil down to a few key choices. The first round of discussion is usually that - what are the basic building blocks of the plan and why is that a good choice? that part really can be a conversation - then you need to code it, and for that, the interviewer is usually happy to be quiet for a bit, if they know what track you're headed down.
Realize that the person on the other end of the conversation has also written code, and knows that it's a messy process. The first round will be a mess. Nothing written in the first 5 minutes will be there by the the last 10 minutes. There's tons of typos and deleting. It's totally OK. If you have someone who's trying to micromanage every line of code on you - it's OK to say - give me a chance to do a rough draft, then I'm glad to take your notes.
Interviewers will nudge you if you've gone completely silent and not prefaced it with a request to ponder for a few minutes. The reason: they have a bunch of data they need to collect about you and your skills. They can't do that if they can't see what you are thinking. If they know you just need a min to collect your thoughts, they can keep an eye on the time, and let you think. But if you just randomly go silent, they are in the dark, and it's poor form for them to just ignore you and hope something useful pops out before the time runs out. Most of the time when I do these interviews, experience has taught me that there are timing milestones where if we haven't gotten a certain amount into the problem, we're in trouble. So I'd rather be irritating and push to see if I can get the candidate to tell me a partial thought, than wait pleasantly and hope for the best.
Practice, practice, practice - do this with a friend, you need an actual human to observe you.
I won't feed you some happy line of hype that it's "meant to be a good conversation" or "you and interviewer are in it together". You are being evaluated and you both know it. I will say, though, that any interview of this sort needs someone who can actually program to be running it and doing the evaluation - so at every place I've participated in this process, the interviewer was an engineer or former engineer (ie, a manager of engineers). These are not folks who by their nature are looking to enjoy someone failing. Worst case, they'd rather be designing actual software with you right now, than doing this fake interview project. :) - more likely, they want to see you succeed competently, both because it feels great to be able to vote "yes" on someone, and because it means maybe they can stop doing interviews, because they've make the hire their team so desperately needs.
