Hi Shir_genzer1
I think I would approach this using separate blocks, randomizers and groupings in order to randomly present the first video (and used an embedded data field to indicate it had been seen), then randomly select half the questions (on separate blocks - again with a grouping to indicate which have been seen). Then I do the same again, but this time with logic indicating only to show the blocks that did not already get flagged as seen.
So for example, your video selection might look like this:
Each of the selections for the randomizer to choose from is checking to see if the block was already seen (an embedded data value that is set in the flow... on the first pass through, none of them is set, so all are available to be randomly selected). Then the block with the selected video is shown, and the embedded variable corresponding with that one is set to "Seen" - when these same steps are repeated later, the video already shown (marked as "Seen") will not be selected by the randomizer step.
(The Group step tells Qualtrics you want those things to happen as a unit together: see the video, mark it as seen; not as two separate steps where it can select one without the other in the randomizer.)
Then the exact same approach is used for the questions, but this time, rather than showing 1 video, you are asking Qualtrics to show (the number of questions, or half of the total question set you described). So if you had a total of 6 questions, you would want the system to select 3 of them after the first video:
(and so one for each question)
You'll notice that I have the survey flow checking for whether the item is "Seen" or not even before I need to. That's because I'm going to do it once, and then just copy the process. Because I built in the check for "has this item already been seen" at the start, I can Duplicate/Move the steps to repeat, so that a different video and the remaining questions will be selected just by having the same flow re-appearing later. If I were to re-order things, the check is still there, and I don't have to worry about it.
(It's a lot of Survey Flow work, but I tend to make good use of Duplicate/Edit/Move to save keystrokes in the process).

Hey CarolK, thank you so much for the detailed answer and solution!
For documentation, I ended up using a different solution, one that only uses randomizers and branches, but not grouping or embedded data.
I created two blocks for each type pf videos. Within each block I had 3 questions with the different video options of that type. Within the block I used the question randomization to only display one of these videos each time.
In the survey flow, I created a randomizer to display only one of these blocks. Later in the survey flow, I created two branches, each is conditioned on the first question of each of the video-type blocks (instructions), and states that only if this question was not displayed, then show the block (the option of "is not displayed" is an option when conditioning on a question). That way, the participants will now see only the type of video that was not presented before. So this was the solution for the random order for presentation.
A similar solution was done for the randomization of questions of the task that is divided into two sections. I created each question from the task in a different block. In the survey flow, I first created a randomizer to display half of all of the questions in the task. After the second video, I created another randomizer, with branches as the number of overall questions in the task, choosing again only half of the randomizer elements. Each branch was for different question in the task, conditioning that only if the question was not displayed (the condition was actually on an answer of the question due to qualtrics' available options), show the block of that question. As mentioned, the randomizer was set to only choose half of these questions. So eventually, with this second randomizer, I was able to randomly show the questions that were not displayed before, and this way, actually randomize the entire task, divided into two sections.