OpenStreetMap is a map created by a community. The map data is available gratis.
That map is not only available as graphics, but also the raw data. Thus, you can basically query everything. There is an API (a programming interface) called Overpass API, which lets you do that. However, you should understand what you're doing, so please read that page as much as you can.
You would start designing the query in Overpass Turbo
A starting point could be this example, which uses my home town, Königsfeld im Schwarzwald as the city. In that case, you already know the country, name of the city and the postal code (78112).
area[name="Königsfeld im Schwarzwald"];
will then give you the names of the streets. You may want to remove duplicates, which exist because streets are split. Create combinations with a few street numbers (ideally depending on the size of the city) and you have generated thousands of realistic data.
Repeat this for a few other cities in other countries.
Visually, this is what you get: