Sadly, the Haida language was probably already in decline during the 1940s and did not have a big enough pool of fluent speakers to pull qualified canidates from.
Not to mention the several language isolates there. Yukaghir, anyone?
I agree that the British, with all the little countries they once controlled, could have easily found their own code speakers. You'd think that as big as Russia was with all the Mongolians and siberian tribes they also could do it.
This brings up another criteria in choosing a language that would work. The Navajo have about 170,000 speakers today. I can't say if there were more or less during WWII, I imagine the numbers weren't extremely different, however.
According to Wiki, which references a Russian site that I can't read, Yukaghiri languages are spoken by 604 people. Again, I don't know how much this may have changed through the 20th century, but let's use this number as an example to establish my point.
Assume we're talking about some hypothetical language that did have 600 speakers at the time some government or other was contemplating such an idea. Now, take those 600 people and figure out how many of them would have been 1) eligible to join the military loyal to the cause, and capable of being trained in the more complex parts of the system that have been mentioned.