Data / Model vs. View / Rendering
First let's clear up one thing: data model vs. view, in the sense described by MVC.
One moment you're talking about one:
How can I implement such a modifiable terrain?
And the next youre talking about the other:
...keep a copy of the vertex and index buffer in memory, modify it...
...You've also tagged your question with both these concepts:
graphics-programming. You should keep them discrete from one another. Implementing the state system on which terrain destruction occurs is completely separate from rendering the current state of the terrain. Remember that data is singular, but that data can be represented in many different ways via multiple views, so you should never conflate rendering with state. e.g. In games, we can represent the world state via first person view and minimap view - two renderings relying on one set of data.
Data / Model
So in the first place - for a 2D game like this, the data model is a 2D array (say of bytes/chars) in which a given location is modified to 0 (air) when the player destroys a tile / chunk of earth at that location. The other 255 values that the byte/char supports is used to identify different tile sprites. This is just a suggestion; you can use many data structures to represent the terrain data model.
View / Rendering
Yes, if you want it to be pseudo-3D like that game, then you'll need to modify vertex / index buffers. It is not particularly inefficient given the infrequency with which you do it. Also, you can use things like
glBufferSubData or buffer orphaning to ensure you make the process as efficient as possible.
If you don't need it to be pseudo-3D, and can settle for plain 2D, then I'd settle for just modifying a screen-sized texture with the changed tiles.