Idea 2 [...] Add a light switch field to the channel called "hasVideo". Update this field programmatically using the onSave event and a plugin. Then I can select all entries if hasVideo is true.
If you're going to write your own plugin I would encourage you to implement carlcs' solution, which is a solid one, rather than going for what is basically a hack.
However, if you do decide to use Low Blocks instead and do the heavy lifting in your template, here's how that could work:
{# Get blocks, using the field ID, filtering by block type #}
{% set blocks = craft.lowblocks.blocks.fieldId(22).type('video') %}
{# Get entry IDs #}
{% set entryIds = [] %}
{% for block in blocks %}
{% set entryId = block.owner.id %}
{% set entryIds = entryIds|merge([entryId]) %}
{% endfor %}
{# Get entries #}
{% set entries = craft.entries({ id : entryIds }) %}
Not super elegant, but it should work. Personally I'm a big fan of keeping templates as logic-free and simple as possible, so I'd probably go for carlcs' solution, myself.
Note: Be sure to switch out the number 22
in my example Twig for the actual ID of your Matrix field.