You could create an options page that holds an upload form, which leverages the WordPress' Filesystem API that handles the file part of it. You just need to specify a solid place where the icon file is uploaded, as you want to keep the favicon data inside template file head
section the same everywhere.
But remember to validate all uploads! Bad things happen when users are allowed to upload malformed data (either by accident or on purpose).
WP Codex also has a page on creating custom options pages, where this upload form could be inserted.