Where to place custom functions?

Organize your code by its purpose: If it creates output on the front end and requires changes in your theme’s style sheet – it belongs to the theme. You don’t have to put everything into the functions.php, split he code into several files if it helps.
For example like this:

// extra functions just for nav menus
locate_template( 'php/functions.nav-menu.php', TRUE, TRUE );

If it should survive a theme switch (Custom post types, shortcodes) or is not related to the theme at all – it belongs to a plugin.

The pure number of plugins is irrelevant: 200 fast plugins are better than one slow plugin.

Template files are for views – they should not contain function definitions that are hard to find there. And shortcodes are a special API, not places.