Directories are always a pain in the neck. My inclination is to set them up using Data Merge, but that requires that you do the proper data preparation. In this case you might need two data files, one for the front with the photo information, and one for the quick reference section, but it might be possible to do it with one, and you'd need to do two documents, then combine them. Using this approach essentially means you must rebuild the entire dierecory for every change, but because you are using Data Merge automation this is not as onerous as it sounds. If you want to be able to simply update, you really need to make the photo section one big text story and have inline photos so if you delte one, the others move up, or you can add one and push the rest down. I think it's easier to maintain an Excel spreadsheet than to shuffle stuff around like that, so I use the data merge and rebuild.
I would definitely merge the photo section, so you need an Excel file with fields for all the text information, plus one with the path to the photo. You can do the quick reference with Data Merge, too, but since it looks very much like a table, it might turn out to be just as easy, or easier to simply place an Excel table. If you are skilled with Excel, you could build one worksheet to use for the photo section, then create a second that references the data in the first for the qr table and not have to maintain it separately.
You are coorrect that you can't do a multiple records per page merge on a facing pages document, but there's nothing to stop you from altering the layout once the merge is completed. You can change from single to facing pages and apply any master you want. If you set up column guides and snap everything to them you can probably even use Layout Adjustment to work with an aysmmetrical margin arrangement. You can combine the sections after merging by moving pages, or by using the Book feature. If the Fileds are on the master page, Update Data Source is available, but I've seen reports of trouble with that command, and I believe I've even seen it drop the photos in my own testing, so I don't know that it has a lot of value in this situation.
On to the TOC and master pages...
Master pages are a good idea as you proposed them, and might be even better using a variable to add the department. This would allow you to use one master page for all departments, and to pick up the department name from the same tag that you use for the TOC. I see you've included page ranges in the illustration above. That's really an index function, not TOC, and I wonder if it's really required? If it is it may be easier to just add the second page of the range manually after you generate the TOC. The reason I say this is that TOC works by finding paragraph styles, then listing the paragraph, along with the page on which it is located. You can list the same paragraph multiple times and use a script to combine the lisitngs (which I do for Index to Advertisers work), but I don't see a reason to do that here. I would set up a paragraph style for department names and make a single heading on the first page of each department. That heading can also then be used to power the variable for the master page headers, and if you don't want it to appear in the final output it can be set to non-printing.