Earlier in the game, I received a few units from allied CS Valetta. The odd part is that these units were H'wachas, a Korea only unit. There was no Korea in this game to gift it to them either. How does this work, and how did it happen?
City states can gift any unit, including unique units (of civilizations not in the current game). For instance, if you have the patronage policy resulting in occasional Great People gifts, you might be given Khans.
From the Civ5 Wiki:
You can see which militaristic city state can give what unique unit in that CS's diplomacy screen.