In a nutshell your needs are completely unsupported by WP API.
Taxonomies in WP are a grouping mechanism. Their primary purpose is to query set of objects, belonging to a group (term) or groups. There is no reverse operation to provide a set of objects and inquire which groups (terms) it belongs to.
On top of that your logic requires additional hop to meta data and to be able to do it in both ways (restrict countries by date, as well as restrict dates by countries).
I see three possible approaches here (complexity ascending):
- Drop the chained requirement. Let users select date and country freely, inform them if there are no results for particular combination. Even Google sometimes says it didn’t found anything.
- Crunch the data with API async and cache the relationship data in some form.
- Write custom SQL that implements the necessary logic with reasonable performance.
Personally I would go with 3 in such situation, but only because I am reasonably confident I can write and maintain such SQL.