Thinking about this has sparked a bunch of questions I hadn't thought of before. For instance, does information encoded with light degrade over long distances in a vacuum? If not, it does seem like a mega-lens could potentially capture such an image right?
Since the vacuum is not totally empty, it does as far as I know.
Just like humid air fogs the picture.
On the lens side of things, as far as I'm aware (not a physicist, math PhD student who is just generally into this sort of thing) there isn't anything fundamental preventing you from collecting this light and building the lens, but from our current understanding of materials science I'm fairly confident it's currently impossible to construct a structure that will stay together that large.
That being said there may be ways around this problem, like I said not a physicist or engineer, but you are right that from an information theoretical perspective if you ignore dust and other things in the way then yes all the information is still there.
Redshift does not come into play at the 'small' scale of our galaxy since the Milky Way is a gravitationally bound system that does not itself expand with the Universe. Even within our local group (eg from Andromeda) it is not an issue since the local group is also gravitationally bound. Redshift only becomes an issue at much larger scales, if you are in another galaxy outside our local group.