Not quite-infinitely expandable human-friendly naming system? This may be a known problem, with known approaches, but I can't find the right way to search for it.

I would like to name points along a line of unknown final length such that their name reflects their relative position to all other named points on that line.  One should be able to insert an arbitrary number of names at any point along the line including outside the existing first and last named points. A lexicographical sort of the point names would always result in a list of points in a monotonic order.  

An order of magnitude estimate of the total number of points to be ultimately named can be supplied up front

Additional restrictions:


Names must be stable, no-renaming after initial assignment
Names may be constructed from a limited character set: 25 lowercase letters a-z with 'L' removed.
The naming scheme should not require an extreme fan-out of name length when adding names either outside the existing points or between two adjacent points. E.g. Imagine that I want to add something before the name 'a', that wouldn't be possible while maintaining linear order during sorting.  Starting with 'b' only delays the issue.  Same for z on the other end.


Names should be of the shortest possible length such that a human could easily glance at one and then write it out elsewhere for most names.



It is highly likely that one would want to insert names between previously adjacent names, and then later between adjacent named points in that previous insertion.

The real-life use case for this is the creation of spatial names for all features of a given kind, say genes, in a species when we don't know in advance the total set of features.  This is because different individuals only contain a subset of the total sequence space that the whole population of organisms encompass.  The problem is easy to solve with static sets of sequences, but not if you allow them to expand at any point along the line (chromosomes) with the addition of new information.  The set sizes of interest encompass 10^5 -10^7 items.
As David points out in a comment, you are asking for an impossible thing because the lexiocgraphic order does not have infinite descending chains, and so you will run out of names if you keep adding points on the far left side. So forget the lexicographic order. (You may keep it if you have an upfront upper bound on the number of points.)

You can use the naming scheme x_N_M where N and M are numbers. Think of this as indexing a point with the fraction N/M. Because fractions are dense, you will never run out of them. To insert a new point on the left of the leftmost point x_N_M, name the new point x_N_2M. To insert on the right of the rightmost point x_U_V name the new point x_2U_V. And to insert between adjacent points x_A_B and x_C_D, name the new point x_E_F where E/F is the average of A/B and C/D.