I don't know who could train Aya. The only person I can think of would be Laura, due to their similar backstories of being killers. But I don't think that would work well.
As for her fatalities? They would be... 1). Charge one hand with electricity, then the other. Place her hands on either side of her opponents head. Say "Clear" and fry their brains out until their head explodes (this is Mortal Kombat logic... everything explodes). 2). Rubs her hands together to build up a charge. Slams her hands into her opponents back. Then walks away. A few seconds later, her opponents chest blows outward. Joke). An electrified french kiss that blows their mind (literally). It just seems to match her personality.
Leon could have Beast as a trainer. Or anyone who has the patience to deal with him, really.
His fatalities? I don't really know. I guess 1). He cuts the opponents throat with his claws, then reaches into the new neck hole with his tail. Grabbing the spine, he breaks it off, yanks it out the hole, then does a sideways spin to build momentum, and impales the opponents head with their own spine. And that's really all I got. Wait... nope, hang on. 2). He uppercuts INTO the opponents gut, right through the ribcage and grabs their jaw, then rips out the skull (MAYBE with the spinal column still attached) right out the front of the face. Joke). He coughs up a hair ball using a localized Sonic Roar to fire it like a bullet right into the opponents temple. Complete with an "Oops" because it was an accident.
Are they kinda lame? Yeah, but to be fair I had to come up with them on the fly. At least they're kinda gruesome and follow Mortal Kombat Logic, which dictates that even with you brain and heart removed, electrified, and put back, you are still alive to feel Raiden blow up your head, then your torso. Mortal Kombat Logic also dictates that when you are frozen, screw gravity.