Storing all the chunks is perfectly fine (Minecraft does this, for example, and the type of feature you're thinking of is probably like the location of villages or fortresses there)
If you really want to avoid storage, you could have a hash function that given a (x, y, z) coordinate that returns whether there's the feature there. Or if the feature only spawns at a random time, function returns the spawn time. So Whenever the player approaches the location at t > (hash(location)) you display the feature.