All of the approaches that you described are in use by different projects.
A project like CryptoPunks generated all 10,000 images and associated them to their ids before they sold the NFTs on chain.
Other projects such as those hosted on Art Blocks work by uploading an algorithm on chain that generates the image when it is minted, based on a random number that is generated in that moment.
Art Blocks is really cool but it is a lot more technically difficult to implement that approach.