Is there a way (or an add-on) that lets me customize the Mail.app toolbar beyond "View -> Customize Toolbar"? At a minimum, I want to add buttons that do "Move to <somefolder>".
Read CocoaDev: HowToAddButtonsToAppleMail. It references a page of links to articles/examples on writing Mail.app plugins. You will also need to do some programming of Mail.app, e.g. using AppleScript - which you can learn more about here.
Here is a year-and-a-half old blog post by a guy who managed to get some useful control over Mail.app from AppleScript. You might use it as a model. He built his with a third-party module but you might find a way to write your own, if necessary.
The scripting of Mail.app might be stable. However, from what I have read - the rules for how to construct a Mail.app plugin may be in flux from one major version of Mac OS X to the next.
That could be enough to discourage you from writing what you want for wide distribution but it might not be much of a handicap for personal use.
I think you can use Mail Act-on for this, it provides Shortcuts for doing stuff with various mails. Not a Visual Shortcut, but a Keyboard one.
Hope it helps,
*Note: For the first time the script works quite long, but all the following times it should proceed much faster.
This approach does not allow to add a button to the toolbar, but it's very close to what you are looking for.