Soldiers should be able to get mechanical implants which improve their skills.
The following is a list of ideas for traits from the forums. I have copied just the ideas that might work for implants. Names probably need to be changed in some circumstances. http://ufoai.org/forum/index.php/topic,6661.0.html
Talented [weapon name] operator Boost to the hit chance with one particular weapon (only if the weapon has been researched). At later game, you might get rookies with bonuses to newer weapons (since they've heard rumors of them and they can't wait to try them out), while you'd still have those seasoned machine gunners and such, adding flavor to the mix.
Medic Unusually skilled medic sometimes gets more healing done with the same amount of TUs. This chance goes up over time as the medic gains battle experience.
Alert gunner Slight bonus to the hit chance when doing reaction fire. Slight bonus to the chance of doing reaction fire. Weapon is fired only if the hit chance is 70% or above, or whatever. Or possibly the trait triggers when an alien is just about to fire. Hit chances and reaction fire chances are increased when soldier is confirmed to have the perk.
Fast aim Aliens have harder time interrupting a soldier who can wave his gun as if it were a pencil.
Quarterback Slightly increased throwing range and accuracy. Bonus gets bigger once the soldier is confirmed to have the trait.
Sniper Option to spend more TUs to do an extra-aimed shot with select few weapons. With increased accuracy, of course.
Die hard Generally more damage resistant than others. Faster health stat growth.
Courageous under pressure Bonus to all skills during base defence missions.
Recon specialist Lowered AP cost for infrared goggles as soon as the trait is discovered.