If you want to increase your speed of movement and kicks, then HIIT type training is going to be your friend.
Your muscles have basically two different types of fibers, Type I, and Type II. Type I are traditionally known as the "slow twitch" muscle fibers, and they are much more efficient at using oxygen (aerobic) metabolism to produce energy. These are generally used in the slower, endurance type of training (light weight/high rep, or such things as distance running, cycling, etc).
Type II fibers can be subclassified into Type IIa and IIb. IIa (Fast twitch oxidative) is somewhat in between type I and type IIb, in that it has slightly higher endurance than IIB. IIB (Fast twitch glycolytic) is the short duration, high force/power output muscles.
So to increase the speed, you need to increase the efficiency of the type II fibers, which is going to result from high intensity, short burst activities. Plyometrics, sprints, explosive lifts, things like this will help recruit your fast twitch fibers.
Here is a decent short article on gym lifting to support fast twitch development, I would recommend something like this once or twice a week. The rest of the time I would devote to high intensity technique training, with speed bags, reflex kicks, spped kicks, etc. You can also add resistance bands to your thighs/ankles to increase complexity.
This is a good video demonstrating the type of drills I'm talking about, and you can look at this question for some stretching ideas, as limber muscles will react faster and have a greater reach.
Just a note: I can't find them at the moment, but I have read studies that suggest you can turn slow twitch fibers into fast twitch. As soon as I can find that, I will add it into the answer.
Workout routine
Note: I am in TKD class 4 hours a week. Two hours on traditional forms, 1 on weapons, 1 on groundfighting/knife defense/similar topic.
During the week, I do a lot of bodyweight and bag work at home. Generally I do 1/2 hour to an hour of HIIT type training, followed by 30 mins of stretching. The exercises that I do are as follows, mixed up pretty much by whatever I feel like doing that day. I do this 4-5 times a week.
- Medicine ball toss - I lay on my back, and push throw a medicine ball (8 lbs) straight up from the chest. I emphasize as little time as possible between catch and throw, and really work on an explosive push. Usually 6 sets of 30 tosses.
- Medicine ball slam - I stand with feet close together, and slam the ball down to one side by twisting my torso. As the ball comes back up I immediately twist and slam it down (both hands) on the other side. 6 sets of 30 slams.
- Medicine ball twists - I hold the medicine ball in my hands, and get into a V-up position and twist with straight legs, again emphasizing speed. 6 sets 30 reps
- Situps - Put legs in a butterfly stretch position. Lay back, hands over head on ground. Sit up and touch floor past feet with hands, making sure to curl torso on way up/down. I usually do 10-15 in between punch or kick sets (See below)
- Pushups - Lower body to ground completely, lift hands off floor then place hands and press. I also vary with clapping pushups, medicine ball under one hand with a roll every pushup, etc.
- Punch sets - Generally it's a single to four punch combo (one, one two, one two three, one two three four), then drop for either pushups or situps. Lather rinse repeat, 10 run throughs is one set, generally 3-6 sets.
- Kick sets - We have a specific 6 kick combination that we do as part of a fitness test, so I'll do that kick combo 10 times with pushups/situps in between each combo.
- Punch/kick combos - 30 seconds of full out combinations, 6-10 sets.
- Agility - I have small agility hurdles and ladders, and I will work on plyometrics and foot speed/movement. Generally 5-15 minutes.
- Plyometrics - Along with the hurdles, I have aerobic steps and I do a lot of the same drills that can be seen in the video and variations thereof.
I also have the Skilz ankle cuffs with bands that I use, exercise bands, and I recently got a wall mounted bodyweight set similar to this that I will incorporate. I also do a lot of exercises such as lunges with weights, burpees, etc. While I advocate lifting, I am not lifting at the moment as I'm still trying to get rid of some muscle mass in my legs from when I was cycling and doing triathlons quite a bit. Our sparring style (Both regular and stick sparring) are very much speed games, rather than the WTF "trembling shock" style of scoring.