Definitely kind of complicated, but it’s a layout I wouldn’t mind adding into the core theme.
Do you have something started? If so, can you show me? It’s easier for me to adjust what’s already done to help achieve something instead of start from scratch.
If you haven’t started, this might help: https://wordpress.org/support/topic/vertical-menuheader-wno-horizontal-header-menu-is-this-possible?replies=10