I think the problem is not as difficult as you have described.

If we look at http://www.wikidata.org/wiki/Wikidata:Notability then you will see that each wikimedia commons page can have a corresponding item. The comment that "a sitelink to a category page in Wikimedia Commons is not allowed on main article items" means that Commons Category pages should link to Category items and not to items linked to wikipedia articles. It does not mean items linked to Commons Categories are not allowed. I fact I believe nearly every Commons Category has a corresponding wikidata category item.

Notability Criterion 3. reads "(An item is acceptable if) It fulfills some structural need, for example: it is needed to make statements made in other items more useful.". I believe that this allows the creation of items for institutions, photographers, books etc as required to describe Commons files. Considering the two examples you identified:

Category:Images released by British Library Images Online
Each of these images can have the statement 'Source:British Library Images Online'. This statement requires a CommonsData Property "Source" and a wikidata item "British Library Images Online". As this wikidata item is needed to complete this statement therefore it meets wikidata notability 3.

Category:Metropolitan Improvements (1828) Thomas Hosmer Shepherd
Again wikidata items can be created for the book "Metropolitan Improvements" and for the author "Thomas Hosmer Shepherd" and for the books publisher (if known). All of these are clearly all considered as notable under https://www.wikidata.org/wiki/Help:Sources. These wikidata items can then be linked to from statements in CommonsData describing each of the images.

Note that this all works without needing to link to the Category Qitems.

In practice this means that if a Commons file is in a certain category then we can know that certain statements will apply to that file. Later, eventually, we can find those files by searching for files to which those statements apply and ignore the categorisation since all the information inherent in membership of that Category has been included in the form of statements. We do not need a "container for structured information for structured information associated with each commonscat". This structured information can just be included in CommonsData, without any separate 'container'. 

Eventually, when the information inherent in the categorisation system has been translated into structured data, and the query system is a lot more useful than today, and the Categories based on idiosyncratic selection criteria have been transitioned into Galleries where they should have been all along then Categories may no longer be needed.

But perhaps we will keep them anyway.