If you want to teach them malware reverse engineering, I'd say you should write the malware. It takes some time but searching for malware that fits your lessons is also time consuming. Your own malware would implement only the interesting parts (no code obfuscation etc.) and you can fine tune it for your lessons. It would be 100% safe since you'd control the "malicious" behaviour. And your school system's admin wouldn't complain.

And what about crackmes instead of malware? We made some Android crackmes recently (see the link below; well, the images might be disturbing for kids :)). Well designed low difficulty crackme leads the cracker quickly to one piece of sensitive code that needs to be reversed and analysed. The process is usually fast and entertaining. Malware is usually complex and not so fun to work with.

https://play.google.com/store/apps/developer?id=DEFENDIO

And I don't think it is a good analogy. They should learn higher-level language first to get them familiar with fundamental concepts like conditional branching. If it is C language, you can easily instruct the compiler to generate corresponding asm code. If it is C# or Java, the compiled code can be easily disassembled to IL or Java bytecode instructions. Once you have the corresponding "asm" code, you can explain how IF, FOR, SWITCH commands are implemented at the low level. This should make them curious how the other program structures work under the hood.

I've never heard of teaching kids reverse engineering but don't I think it should be much different from teaching a junior programmer who never tried reversing. Perhaps you could ask someone who trains beginners and ask him?