You have a couple options here:
- Force every user to allow programmatic access to the VBA project for their documents, and use VBA automation to add code. This works nicely when you have programmatic access, but this can be difficult to assure.
- If you're not using Visio 2013, you can actually save a document as VDX (xml) and replace the data for the VBA project with your own (you'd save out a document as VDX manually, and copy out the chunk of data for the VBA project). As I said, this wouldn't work with Visio 2013 since they seem to have eliminated the VDX format. You probably can get away with something similar with the VSDX XML format for 2013.
- You can 'migrate' everyone's documents to a new VST file you provide. This would just involve copying and pasting all the content from a document into the new document that has your code in it. You have to be careful though to make sure all the document- and page-level data comes along, too (meaning DocumentSheet and PageSheet and any Document XML properties that may be important, and attributes like Author, Description, etc...)
Item 1 is the easiest, aside from the pain getting programmatic access to VBA Projects, unless you can have people send you documents to migrate.