I guess the only way to accomplish that is to set up the new blog on my own server where I will have access to a .htaccess file. That is, I can't use any hosted blog like blogger, tumblr, wordress.com. Is this correct, or are there any hosted blog services that will give you this fine-grained control? Or are there any things I can do on the domain registrar side?
Alternatively, is it a good or bad idea to route all traffic to my blog through a VPS I have, so that all the old blog post addresses go to the right place on one of the hosted blog services? (I'm just trying to avoid hosting my own blog, since I assume there are a lot of headaches involved)