How to force a theme to use a sitewide custom menu
How can I insert a sitewide menu?

You can use Context to insert menu blocks into regions. 
Contexts can be set to be site wide. 
Make sure that your theme supports the region into which you are inserting the menu block.  The region should be defined both your theme's .info file and also it's relevant templates (generally the page template).

Making a menu with a custom template

You can use the devel_themer module to sniff what templates you can implement to override the menu's default theming.