Updated answer (2022):
Since my previous answer from 2019 (which I don't recommend), I found two other possibilities: pyramid plots or network visualization. If you have data similar to the dataset described in my question, both solutions involve either data wrangling and/or collecting additional data. Here is my approach for these two solutions, that can probably be improved further:
Solution 1, split barplot/pyramid plot:
Heavily inspired by xan's answer (thanks!), but with a tweak: a barplot, similar to a population pyramid, where the unit of measurement is an individual refugee, instead of a group of refugees. So the Y axis is no longer categorical, but represents the cumulative number of refugees. In addition, the X axis is split between two sides. In my case, it required transforming the dataset, but it wasn't really complicated to do.
Below is the result (probably clearer than my explanation). The vertical red line represents the number of refugees, the bars on the left represent the distance to the nearest administrative center, and the bars on the right the distance to the nearest big city:

Example of reading: about 200 refugees were at 40 kilometers or more from an administrative center or a big city. Additionally, a relatively small group of refugees was located in an administrative center which itself was at more than 60 km from the nearest big city. Finally, about 600 refugees were at 20km or more from an administrative center or a big city.
Advantages of this visualization:
- It gives a pretty good idea of how many refugees are very distant or very close to big cities/admin centers, depending on what you're interested in.
- You can identify outliers, for example the very noticeable long blue bar on the top of the graph.
- You can identify groups based on their distance to the nearest city of interest. Note that this is different from the original groups, more on that below.
Disadvantages:
- It may require an explanation if you communicate the graph to an audience not familiar with data visualization.
- You lose the information about individual cities, for example if a group of refugee A is in a different city from group B, but both groups are at an equal distance from an administrative center and from a big city, you can mistakenly think they're originally from the same group. It might be possible to tweak the visualisation further to distinguish original groups from each others. Maybe something similar to Xan's answer, but including the "right/left" split on the X axis, instead of overlapping the two categories. I'm not sure it would work with a really big dataset.
- You may overlook the refugees who are at a "0 km" distance, i.e. the part of the vertical red line without bars on its right or on its left. A solution may be to tweak the dataset to add 1 or 2 kilometers to the 0 km distance.
- Depending on what your original dataset looks like, ending up with this kind of visualisation might be difficult, but it's a programming issue, not a visualization problem.
Solution 2, network visualization (requires additional data)
In my case, network visualization has the advantages of a map, without some of its downsides, e.g. if some cities are very distant from each others (e.g. hundreds of km), it somehow obfuscates the distance between refugees and cities, making it apparently very small in comparison (i.e. 60 km may look very small depending on the map scale).
Depending on your dataset, network visualisation may require data wrangling and additional data (e.g. in my case, it may require identifying uniquely each administrative center and each big city), but it might be worth it and may give additional insight.
Here's a very crude example, but you get the idea, i.e. we use cities and groups of refugees as nodes (with varying colors and sizes), and distances as edge length:

Information represented: the relative distance (=edge length), the size of each group of refugees (=circle size), the type of city (=circle color), the city size (=circle size).
Advantages:
- It allows to identify important cities, clusters, etc. Additionally, the data wrangling process may allow you to perform network analysis on the transformed dataset.
- On a map, if the big green circle and big blue circle had been distant for hundreds of kilometers, it would had been very difficult or impossible to plot all these information without creating clutter and overlapping circles. Network visualization removes this obstacle, e.g. if in this visualization we treat the direct distance between the two big blue and green circles as irrelevant.
Disadvantages:
- You might only be able to visualize relative measurements (distance, size). To get the exact measure you're interest in, you'd probably have to refer to the original dataset. For example, you can see that some groups are relatively closer to big cities than others, but you don't know by how many kilometers exactly. Maybe adding some textual information on the graph could solve the issue (e.g. adding a label on each edge mentioning the number of km), but a risk is to clutter the graph. Otherwise, using the legend may or may not do the trick, but I think it depends on your dataset.
- Circle size is used to represent two different variables (group size and city size). It does not necessarily create a problem of interpretation if you use a color to distinguish refugees from cities, but it may require some manual customization to avoid some circles becoming too big or too small.
- Depending on the tool you use, it may take a while to create a correct visualization, i.e. choosing the right algorithm (here I used Force Atlas followed by expansion, and tweaked a couple of things manually), customization, adding a legend, maybe transforming the data, etc.
- Not sure of how well it works if you have a boatload of data, in particular if you need to perform a lot of manual tweaking. Solution 1 might be better in this situation.
Old answer (2019):
I don't recommend this answer, but leave it in case it might be useful for other use cases.
I finally chose to use a bivariate kernel density estimation plot.
I had to transform the data to do that:
Refugee ID | Host city/town | Km from the nearest admin. center | Km from the nearest "big city" (>20,000)
1 | City A | 22.5 | 22.5
2 | City A | 22.5 | 22.5
3 | City A | 22.5 | 22.5
...
853 | City I | 40 | 50.2
Then I estimated the bandwidth with statsmodels KDEMultivariate, and plotted the data with seaborn.kdeplot:

Some information is lost, but I find it's a good compromise.
I find that the diagonal is less disturbing than with a bubble plot, as the density and the separation in three groups is more eye-catching than the diagonal form. It allows to easily identify groups in the data.
There may be a better solutions to this problem, but I hope this suggestion will at least help other people.