I’m not sure how Storj does it, but that wouldn’t be a problem when done together with chunking. The network would still work with chunks (that is, not gigabytes of data) but the chunks themselves would be split up into numerous smaller blocks, only a few of which would be required to restore a chunk, be it either as a normal read or as part of recreating a lost block.
Data maps would refer to chunks as now, but chunks wouldn’t store the data itself but a public “secondary data map”, pointing to the blocks the chunk is made up of and those blocks would contain the actual data. It’s a trade-off between complexity and storage space, with some latency related considerations thrown in.