Regarding the coordinate system:
In order to address individual tiles, you will need some kind of origin (a 0:0 point). In order to allow the playing field to expand in every direction, you will also need negative values. This will give you a world which stretches from -2.147.483.647 to 2.147.483.647 in both directions, which is "large enough" to seem infinite for most sane players (depending on the game concept, of course).
To allow an even larger world you could use floating point numbers. But the disadvantage of floats is that you can not rely on their accuracy. This might introduce some strange and obscure bugs when you reach extreme distances from the origin, like in minecraft.
Saving the state of 2^64 tiles is more than any database can bear, so you should only save those tiles which are worth saving (those which are already discovered and changed by a player). To avoid infinite growth of your database you might consider to discard the state of tiles which were not visited for a considerable amount of time, but that's a gameplay decision.
But how do you save them?
Saving the whole world in one huge data structure would mean that the whole world needs to be kept in memory all the time. When the world is extremely large, this could result in unacceptable memory usage. But storing each tile individually in a database would mean that you need a lot of database queries all the time, which can become pretty inefficient.
A good compromise is to work with squares of uniform size of 16x16, 256x256 or whatever is appropriate for the specific use-case and store and retrieve each of them as one entity in the database. Such sections of the map are usually referred to as "chunks".
Regarding the procedural generation:
An interesting aspect of pseudorandom number generators is that they always return the same sequences when they get the same seed value. When you use the coordinates of a chunk as the seed value to generate it, it will always look the same. That means you don't even have to save the static information about a chunk anywhere, because you can just re-generate it on demand. Only the dynamic information (in this example, the letter tiles) needs to be stored in the chunks. When a player just visited a chunk without leaving any traces behind, you don't even have to save it at all.