An add-in sounds ideal for this. Creating one in XL2004 is the same as in other versions - File-Save As, change the type to 'Excel add-in'.
You will need to create some sort of menu system for running the routines though - my preference is to build the menus in code when the add-in is opened.