I am making a 2D tile-map based game, and seeing as I tried and thought of many different ways of holding data and rendering, I've finally come here to ask you guys for suggestions.

My problem is like so:
If I make rendering fast, editing the data is slow and painful.
If I make editing data easy, rendering is slow.

I started with the second approach some long time ago (in another game, in fact), before I even knew what buffers and shaders are.
I iterated over a 2D tile map, rendering each tile in turn.
This is super slow because of the huge amount of buffer and texture swaps, and the rendering calls.
However, it made editing the tiles (e.g. changing textures and such) a simple act of changing a number that indicated what texture to render with.

Right now I went to the opposite direction - one gigantic buffer that holds all the tiles, all the textures are combined into a texture atlas, and it is rendered in one call.
While this is super fast (so fast that instead of rendering only the actual tiles visible with a few rendering calls, it was faster to just render the whole thing in one call), it makes editing a big horror movie.
To change textures I need to change data on the GPU, since the texture coordinates must change.
If I want to draw tiles with a different texture, I have to hold two sets of texture coordinates which is a big memory footprint (and I do want this, to show what tile is going to be drawn when editing the tile map in real time).
This is both painfully slow (relativly speaking, but it does jitter if a lot of tiles are edited simultanously), and very annoying to code.

I thought of other ways, such as separating the tile map into groups - one per texture they use - but that makes editing even more slow and painful.

So, I am wondering if there is some way to enjoy both worlds - easily editable data, and fast rendering.

I am using WebGL, by the way, so many features I wouild have liked to have from OpenGL 3+ are not there.

Currently I have only one layer. I made also arbitrary "objects" which are just sprites with an abitrary size and position (including depth), but I think I am going to move to multiple layers of the tile map itself since editing these objects is one big mess both in code and for the user, while editing the tile map is easy pie for the user.

By changes I mean tile editing at run-time.

My design basically has "tile type" objects, with every tile referencing a type. The type includes, among other game-logic related things, the texture the type uses, which gets translated into correct texture coordinates at initialization (since the texture atlas is made at initialization too, from a sequence of actual images).
In my old code I simply changed the tile type for any tile I wanted, something along the line of "tiles[y][x].type = whatever", but since I am now using a texture atlas, I also have to change the texture coordinates in the UV buffer.

I am not sure what you mean by storing the map indices and generating correct UVs based on those.