Best approach for storing complex data structures and tables (iOS and WebPlayer)

Let me preface by saying, I've not done WebPlayer or iOS Unity work.

Have you considered using ScriptableObjects? You could make classes for each type of data you want to store and then just make assets for each instance you need. This way you don't have to deal with parsing the data into a format that can be used by your code since it already is. You also have you data in first-class assets and gain all the built-in Unity support for assets, including only including the ones that your scene actually references. You can also interlink directly from asset to asset (no need for name or id references).

I think the XML would work, and is easily expandable. You could also implement some kind of hash table (to retrieve objects quickly) once the file is local.

If the data is on an external server, can't you just download it to the local client and then access the file? You could the have unity read in the file into a hash table.

The only downside to hash tables is when you get over half full of elements (as more collisions and iterations occur), and when the hash table needs to be resized. Otherwise a hash table is super efficient on retrieving data. So in this case, just store the data into a hash table (which is most cpu intensive part of the procedure) and then retrieve the information during runtime.