It depends how long you want to wait and how much you are willing to pay. With empty mempool, 4 MB per 10 minutes is quite slow transfer, so to push 4 GB video, it would take at least 1000 blocks, so about a week. Also, assuming one satoshi per stored byte, it would cost 0.01 BTC per megabyte, so around 40 BTC for storing that with the lowest fees.

Also note that you can upload any data in a hidden way. For example, you can use some HD wallet to generate pseudorandom keys, then you can tweak them with 32-byte chunks from your video file. When all coins will be moved back to your wallet and you will have a lot of confirmations, then you can release your xprv and release some program that will extract that data.

Another thing is you don't have to actually pay that 40 BTC to do that. If you are some big exchange with some significant liquidity, then you move a lot of coins in your daily transactions, so all that you need is tweaking keys with chunks of data you want to store. Also if you can produce deterministic signatures, then you can tweak them too. So the true cost is not really 40 BTC, but rather 4 GB / 32 byte keys = around 2^27 keys. If you assume each output has one public key and one signature, it would mean the total cost is spending 2^26 outputs. So if you have that much traffic with random keys, you can upload videos for free, just by switching to deterministic keys and signatures, and tweaking them with your data.