In addition to the other answers, there are some things you can do to speed this up if you want to do a little bookkeeping with regards to "collecting" a bunch of pixels into blocks of "known similar state." E.g. you could store the height of the highest terrain piece, so you can take for granted that the missile won't hit anything as long as it's above that. You could also store the height of the lowest "air" space, so you'll know that if the missile gets to that altitude that it must have hit something (although this might be best used as a sanity check). Going further than this, you could store rectangles representing areas that are all terrain and other rectangles that are all air, but that might be more work than value.
Ultimately, the best method is probably going to be "store off the height of each terrain column" and then just compute the missile height at each step of its path. I can't speak to more modern games, but I believe that when you made a "cave" in Scorched Earth, that the terrain above that cave fell straight down, leaving no overhangs. If you want overhangs the work will be a little greater, but it will be an extension of this basic idea. (Hint: get the basic idea working first!)
Since your terrain is presumably completely arbitrary, there are no shortcuts. Even if you forced your terrain to be a spline or something, that'll get upset once you start destroying it and line-spline intersection tests are iterative and non-perfect or exhaustive and pointlessly slow for your type of problem.