Screenshots referred to below are broken.
Getting the grenades
Despite what the mission name suggests, the objective here is to kill all the enemies. In other words, getting to the engine without killing all the enemies won't complete the mission. Thankfully, the in-game objectives screen makes this very clear. Let's get started.
Ignore the Green Beret for a moment. Instead, select both the Spy and Thief ('Ctrl' + '5' + '6' or draw a box, whatever works for you). When the soldier at the corner of the carriage (Guy #1 in the screenshot) looks away, quickly move them both to a spot behind the officer (Guy #2). Knock out the officer and let the Spy wear his uniform. Exit the Spy through the door there (leave the Thief in the carriage for now).
There are many carriages in this train. In order for you to follow this walkthrough easier, here's a screenshot of the complete train. The carriages are numbered (1) to (9). My apologies for the crappy look (the train is not even straight!). The image was made by rotating, pasting and squashing many screenshots together. Anyway, you get the idea, no?
Distract #4 with the Spy, and kill #3 with the Green Beret. For this and all future executions, the Green Beret's knife is the ideal weapon. Also, there is no need to worry about the bodies. Kill and move on. Also note that the Green Beret and the Thief can jump from roof to roof, whereas the Spy is not so athletic (he has to climb up and down ladders). All right, go on and kill #4 and then #5 with the Green Beret.
Move the Spy and distract #9. Make him look away. With your Green Beret, knife #6 and #7. Watch #12's field of view. When he turns around, knife #8, #9, #10 and the lieutenant (#11) one after the other. Hide your Green Beret in the shadows at the foot of the ladder. Now, get your Spy to go over and distract #13. Again, when #12 has his back to you, climb up with the Green Beret and knife him. Now, watch #14's movements. At the right time, walk/run past #13 (behind his back) and go and kill #14.
Carry on the forward march and use your fists on #15 (to avoid alarming #16 nearby). Then knife #16 and #17. Jump over to the roof of the next carriage, i.e., (9). This will alarm #18 (mechanic) and he will come running to punch you. Knife him. Go over and finish off #19 and #20 (you can either knife them both swiftly, since they are next to each other, or you can shoot them with a rifle, if you have picked up one along the way).
Now, come back to carriage (8) and climb down the porthole (where #15 was). Stand back and throw cigarettes to lure #21 (see the screenshot). When he has passed by your ladder, climb down and kill him. Kill #22 also. Pick up the grenades from the crate and climb back out.
Using the grenades
Run back across the roofs and kill #13 (whom the Spy has been distracting until now). Now, get the Spy to climb down and enter carriage (7) (from the left). Inside, there will be a lieutenant pacing near the door. Distract him with your Spy (and make him look away). Now, get your Green Beret also to enter the carriage and knife the lieutenant. Also knife the officer who's looking out through the window. There's a dog here that can smell you and raise the alarm if you move any closer. The only way to kill the dog is by using grenades (which will also of course take out everyone in the vicinity). Throw two grenades in quick succession to take out everyone in that carriage, including the doberman.
Next, exit the Green Beret the same way as you came, and enter carriage (6) (before you enter, equip your knife and be ready). This carriage is full of mechanics only. It's a melee! Knife them all. You'll get punched a few times in the process and probably suffer some damage to health, but that's the best you can do. You will probably die if you try to shoot them all down. You can't use grenades because this carriage has art goods and you'll fail the mission if they are damaged.
Move on to carriage (5). There are four soldiers here. Since you enter from the right side door, you won't get noticed by them (they have their backs to you and are facing the other door). Once again, the knife is your best weapon (as before, you can't play with grenades because of the art goods, and trying to gun them down will only likely result in suicide). Bring the Spy along if you want some help in distracting them while you cut their throats.
Move on out, onto the flat, open carriage (4). Leave the soldiers here alone for the moment. As before, you can walk right through them, and they won't notice. Now, climb up onto to the roof of carriage (3) and make your way to the entrance of carriage (1). Standing outside the door, lob grenades inside (by clicking on the door). Keep throwing grenades inside until the whole battalion is dead ("examine" the door (hotkey 'Z') to make sure). There's a crate inside this carriage with more grenades to resupply your stock. Remember, if you already have some grenades left, you won't be able to pick up all the grenades from the crate. You can either 'Shift-Click' to top up your quota, or come back later when you have exhausted the ones you have.
You're almost finished! All that remain are the chaps in carriages (2), (3) and (4). Since you should by now be an expert in assassination, I will leave it to you to take care of the rest. Basically, just use a combination of distraction (with the Spy), cigarettes, knife and grenades. Feel free to use guns/rifles. Combined with the auto-aim mode, they can be quite lethal. Your long-forgotten Thief, waiting patiently in carriage (3) can also lend a hand. Once you dispose off the last soldier, mission accomplished!