Except for the upcoming BlackBerry Passport (which may or may not be offered at Koodo), I don't see any other device that fits your needs, Reuben. And I'm not even sure the Passport has a removable battery. It is, however, a larger device with a larger keyboard and a larger screen.
Current Android, Windows and Apple phones have no physical keyboards.
You may be able to find something from a couple of years ago, but then its performance will be underwhelming at best.
Yeah, the passport is your only bet, really. Q10 is good but it has a smaller display. The keyboard on the passport is very wide but not very tall, so it might feel uncomfortable. I'm not too sure on it.