It might be worth contacting Birmingham City Archives, to see if they can help you. (They night, for example, have kept phone directories from the period, enabling them to simply look up 'International Stores' to see if there was a branch listed in Alum Rock):
[email protected]