If I have a CPT "movies" I know I can have various taxonomies eg "Director", but how can I store further information such as "director's nationality" for any one particular director ... or is this possible using WordPress?
why don't you take a look at this I think it it is what you are looking for
Honestly, I can't help but think that you are trying to use the taxonomy system for something beyond what it was meant for and that you should be considering post meta or a custom post type.
Or, you should be using multiple taxonomines-- one for directory, one for the director's nationality, etc.
I would say to use the multiple taxonomies, or create your own table to hold the taxonomy meta. I worry about performance though. The taxonomy queries are complicated.