A byte can hold one of 256 values (0–255), and luckily there are way more than 256 blocks in Minecraft, so I can hand every single byte its own block.

This was not always the case. It is now since they moved (many years ago) to their new ID format, but at one point there were less than 256 blocks, and items would start at ID 256 (Iron Shovel). Not super relevant today of course, but just a fun bit of history.

Anyway, two other things come to mind:

1. You could encode files directly into NBT data for an item or entity. You might need to split files across multiple tags though. It'd be funny to see armor stands representing files on disk, for example.
2. You don't need to map bytes 1:1 to blocks. It's possible to have a palette of more than 256 blocks, and encode the data in a different base, like say base 300 or so, to make the encoded data more (spatially) compact.

Cool project. It's a fun idea.