What about laser engraving ? While it sounds rather fancy, I know it is possible to use it to engrave random stuff to almost any material (IIRC there was a video of a guy having his name laser-engraved to the lid of his notebook) with quite nice precision. So making a custom pattern corresponding to the labels and laser-engraving it to the keyboard might work.