I assume there must be something (not arduino) which converts analog to digital.
Correct. Not only that, if you want colour, you have to decode the composite NTSC signal into its three components and digitise them separately (though the colour components have a very low bandwidth compared to the luminance signal).
If the video is already in digital format, would I be able to stream it over Wi-Fi using Arduino + Wi-Fi shield?
It depends what you mean by "digital format" - simple baseband digitised video, JPEG, motion-JPEG, MPEG or H264, or...
Baseband it probably the worst from the point of view of the AVR because there is almost nothing about the AVR that can handle the datarate, except at very reduced resolution, even if the processor is acting as a pass-through...in which case, it might be better not there at all.
The others require the video source to do the encoding, because the AVR simply isn't up to the job, and again, it is acting as a passthrough.
Simple arithmetic illustration:
Raw eight bit
monochrome image at 160x120 resolution = 19200 bytes per frame.
At 30 frames per second = 576 000 bytes per second.
Even if you compress it (somehow, somewhere) at 30:1, that's still nearly 200kbit per second for a low-res, mono image.
Colour, at best, will add typically half as much again, maybe even as much again, i.e. doubling.