I've felt the same way for a long time... and the only way to get over it is to practice. Buy a whiteboard and practice at home. Buy some books (e.g. http://www.amazon.com/Introduction-Algorithms-Edition-Thomas... and/or http://www.amazon.com/Cracking-Coding-Interview-Programming-...). You can also subscribe to http://codingforinterviews.com/.
Not exactly an answer to your question, I know. Most startups I know in SF/Bay Area at least do a technical test (either coding or just regular questions) on the spot. It is stressful, but as anything, you can learn how to do it.