Can’t it be more optimized? Making game with destructible environment would be cumbersome with such limitation. It may be that you try to recalculate whole map, since you know x/y of tile you are modifying, why can’t you just recalculate that part and leave rest as it was?
I can do that. The only problem I see is that empty tiles will be also generated (as I have to know where the tile is in the vertex array)
It’s not problem if it will be faster.
I’m currently doing some tests, and it seems working. 
This huge optimization will probably be in the next GD version.
(I can even build a custom GD version for you so you can test it)
That would be nice. With current state of things, replacing tiles is basically useless, even for just level editor.