Since you already have this being handled via blocks, I would approach this using randomizer+grouping+embedded data in order to randomly present the first video (and used an embedded data field to indicate it had been seen), then on the second instance, 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 randomizer 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 as Seen, 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.)
This also means (your second bonus question) that yes, you'll have an indicator to help you tell which videos were seen by each respondent (EG if Video1=Seen, they saw Video1). For cleaner reporting, you could have a set of Embedded data steps at the start of the survey that set all the Video values to Unseen, since reporting doesn't work well with blank values, then all videos would have a value assigned (Seen or Unseen) for each respondent.
(That may all look like a lot of Survey Flow work, but I find the Duplicate/Move and a little editing make it fairly streamlined to do. BTW you'll notice that in the image I have the survey flow checking for whether the item is "Seen" or not, even in the first randomizer, before I needed to. That's because I'm going to program it all once, and then just copy the entire thing for the next randomizer. Because I built in the check for "has this item already been seen" at the start, I can Duplicate the entire Randomizer for your Q1 and just move the copy into position for Q3, so that a different video set will be selected just by having the same flow re-appearing later. Also, if I were to re-order things in the flow, the check is still there, and I don't have to worry about it. So basically I did "extra" steps at the beginning to save me steps later.)

CarolK, you are a certified genius - thank you so much!

You're so welcome, I hope your project is a great success!