Firstly, I'd like to point out that your instinct is 100% correct - always take to the time to gather your thoughts and never assume that you are supposed to answer straight away. I have a friend who was unsuccessful in his final round interview because he thought the interviewer wanted him to answer straight away and then was given feedback that he was unstructured. This sort of situation is much more common than what you describe, in my experience.
That being said, I agree that there's an extra challenge here to guide the interviewer through your thinking as you are doing it. The interviewer knows this, they know you are thinking out loud, so of course they are not expecting the same answer as if you were reading your notes off a page, so it's okay if it's a little messier.
My main advice here is: After you finish, restate everything quickly in a more organized fashion. I find that interviewees don't do this often, but it's an easy way to make all your answers better and you can do it at almost any part of the interview, including behavioral to improve your answers. There's no rule that you only get one chance to say something and this is a good technique to improve your performance.
Hope this helps, happy to provide more details through the chat.