Standard pKa measurements
pKa is, as you mentioned, commonly measured in water. This worked well initially, but as chemists got more ambitious in their measurements, they began to come up against the levelling effect, whereby the acidity/basicity of the compound being measured was limited by the acid/base properties of the solvent being used to measure it.
To a certain extent, this was mitigated by moving from water to a solvent that is unchanged over a wider range of pKa (the range of pKa is known as the discrimination window), DMSO being the example chosen. This change to DMSO allowed the pKa of far more compounds to be measured. DMSO has been used to measure the pKa of LDA, the example you gave.
Even in cases where DMSO is unsuitable pKa may be measured in other solvents. There is however an issue with using different solvents to measure pKa in that the values are not directly comparable since different solvents affect the ease of protonation/deprotonation. The discrimination windows of several solvents are given below (Source: Wikipedia).
Standard pKa measurement is carried out by dissolving the compound in the solvent and titrating in acid/base slowly, whilst measuring the pH change, which can be done in many ways. This gives a curve from which the pKa may be read off (pKa is the point at which the compound is 50% ionised).
Measuring pKa of weak acids
Whilst pKa has been determined for many common chemicals, there are instances where pKa will be extremely high/low. In these situations, we can abandon the direct measurement as described above, and look for some other way of doing it.
-A brief interlude- To give an analogy that may (or may not) be more familiar. In medicinal chemistry, logP is an incredibly useful property. It was traditionally measured by partitioning the drug molecule in-between octanol and water and seeing how much of the compound ended up in each layer. This was laborious, and so medicinal chemists moved from directly measuring logP to carrying out other analysis from which logP could be derived. The common way of doing this is to use a column (similar to chromatography, but specially adapted). The chemist first runs a set of samples with known logP through the column, followed by the compound being studied. By looking at retention times and then comparing and doing some maths, a calculated logP can be obtained which is generally fairly reliable.
With pKa measurement, the situation is a similar in that we can indirectly measure the pKa and extrapolate.
There are, however, two separate issues here. A first problem is that pKa measurements at the extreme are just difficult (i.e. very small or very large) due to the titration curve becoming very difficult to measure accuratly, it isn't impossible however. This is really the main issue.
The other problem is related to levelling, but as you can see from the table above , we do have solvents available to measure over pretty much as wide a range as you could ever want (note: if you're considering measuring a pKa in hydrofluoric acid, you should probably reconsider why you need to measure it in the first place).
The following paper (free to view) details the most common direct and indirect methods of determination.
From my experience, there are three methods I think are worth discussing here as alternatives to direct pH change measurement. . .
HPLC measurement in which the pH of the mobile phase is varied. As the pH changes, the compound may ionise, which changes its retention time on the column. This may be used to extrapolate pKa by comparison to samples of known pKa. The HPLC columns used now are able to tolerate the use of highly acidic/basic mobile phases for pKa determination.
NMR measurement in which we 'titrate' in the NMR tube, adding acid/base, and watching as the chemical shift changes. This has allowed some super accurate pKa's to be measured.
Comparative measurement in which a compound with a known pKa is reacted with our compound for analysis, and we see the extent to which they protonate/deprotonate one another. By looking at this equilibrium constant we essentially can derive the pKa.
Last, but not least...
Computational determination of pKa
Although not a 'measurement' of pKa, in silico computational methods are becoming increasingly accurate. This is especially true within a normal pKa range, but has also found applications with highly acidic/basic molecules. Some common packages for this are ACDpKa, Epik and Marvin.