Here's how to use the "replace by he/him method" here: "He was sheltering him" > "who was sheltering whom". So "..and it was impossible to know who was sheltering whom" uses "whom" correctly, according to that rule.
As you may have seen, Johnny, some commenters think that you may not be aware of the fact that the prescriptive "rule" or "method" you mention isn't actually an accurate guide to using who and whom appropriately from a descriptive point of view. That's really a separate topic, and there are many other posts on this site that deal with it, such as ShreevatsaR's and nohat♦'s answers to "What’s the rule for using “who” and “whom” correctly?".
You can also see notes on the usage of whom in dictionaries like Merriam Webster, which says
now often considered stilted especially as an interrogative and especially in oral use
Observers of the language have been predicting the demise of whom from about 1870 down to the present day. [...] Our evidence shows that no one—English or not—should expect whom to disappear momentarily; it shows every indication of persisting quite a while yet. Actual usage of who and whom—accurately described at the entries in this dictionary—does not appear to be markedly different from the usage of Shakespeare's time. But the 18th century grammarians, propounding rules and analogies, rejecting other rules and analogies, and usually justifying both with appeals to Latin or Greek, have intervened between us and Shakespeare.
This information is relevant to your question because "who was sheltering whom" is an interrogative use of "whom". It would also be correct to say "...it was impossible to know who was sheltering who". "Whom" is possible, but not required after "sheltering". If you are writing dialogue, it may be a good idea to avoid using "whom" in sentences like this unless you want to give the impression that the speaker is a pedant.
I don't know of any grammatical reason to use "whom" instead of "who" before "was" in your sentence, or any group of speakers that would tend to use "whom" in this context, so I would advise against doing that.