I'm not sure on the pacing thing. I love the Clifford Stoll talk from TED and he's flying all over the place the whole talk. Admittedly its not actually pacing.
For those who do want to get better at public speaking (including me), I'd highly recommend the book "Presentation Zen."
And for those too cheap to buy the book, this 70-minute Google talk by the author of Presentation Zen will give you most of the information for free: http://www.youtube.com/watch?v=DZ2vtQCESpk
I see your point, but when I hear "exceptions to every rule" I want to explore the boundaries of those exceptions. I think that presentations are creative performances, essentially, so it's likely that the number of exceptions are going to be large.
It's just like every other artform - the rules are there to give people a framework they can work from, but the best performers break the rules. Clifford Stoll is a great example of this.
1) Video tape yourself giving your talk. Tape off a section of your floor, set the camera up on a tripod, and give your talk (complete with powerpoint or whatever you're using). Then watch it. Ask yourself, "Would I want to listen to this person?" Probably the answer is "no". Figure out why, and fix it.
2) Just like you should walk with purpose, your hand should communicate with purpose, too. Too often speakers flail their arms wildly about, rather than using them as a tool of communication.
I don't think you need to be too nervous at technical speaking engagements. In my experience, most people just show up to hear you say the name of the talk, and then they tune out and start using their laptop. So if you pace around the stage, they won't notice, 'cause they're off in some other world.
(You could say, "Well, that's because all your talks are so boring.". Maybe, but this happens at even the most interesting speaker's talks as well.)
Make sure to practice at least a few times in front of some friends to get the jitters out. I have to present once or twice a semester and I always need a few dry runs to get the jitters out. If I really was presenting to a large audience I would have to practice many, many times to have it all down pat and not look nervous.
For those who do want to get better at public speaking (including me), I'd highly recommend the book "Presentation Zen."