Hey man, I follow. Yeah, a good tutorial system is essential to keeping beginners - if it's too hard there's not going to really be an in and many people will turn off the game because of it.
There's a couple of ways I think that could be used to implement tutorials -
Firstly, some kind of simple movement based map (think strafe/bhop, RJ, doublejump) which leads into a 1v1 bot match (think the Quake live tutorial) - gets you set up with the movement in a simplistic way quite quickly and then the time it takes you to complete coupled with your bot performance helps get your initial skill ranking. (Skill ranking is another matter entirely, but it might be something to think about)
I like your idea of training games: Maybe a tag game mode? I'm not thinking so much like freeze tag, more one player with a Bolt Launcher, the other players trying to evade. Get hit by the bolt launcher and you're it. Works reaction skills for the BL and player movement. Or how about something similar to Counter Strike's gun game? You have to get x amount of kills to move on to the next weapon, first to get all of them wins. That should help gain familiarity with different weapon types. And borrowing from defrag, you can always run a race mode - you might even want to put a twist on it for duel maps, compete for the best time getting a full stack?
They key is making these available in playlists from the main menu, instead of relying on players to go and find these gametypes on private servers - the modes are there, it's just how you present it to the player.
All in all I think you're on the right lines - it's about taking complex ideas/movements and breaking them down to a level where the basics become the game. Then it's down to the player to put 2 & 2 together to make 4