When should I add a new tpl.php file, and when should I implement a theme function?
There are two types of theming something (theme('function', $args);)
Functions
The call to theme will result in a theme function being called: theme_foo with the arguments which will return the HTML string to be outputted. These can be overwritten by creating THEME_NAME_foo function in template.php
Templates
For template theme functions two things happens, preprocess_foo functions are called which will populate variables for the template. These can not be overwritten, but new ones can be added, as the alter an array which will contain all the variables used in the template by reference. The template file itself can be overwritten, by create a file withe the proper name. With use of suggestions, some can take precedence over others in certain cases. (node-forum.tpl.php used for forum type nodes vs node.tpl.php used for all nodes if no better match exists.)
Answer
So in short, it depends on the definition of the theme function if you should use

a template and/or preprocess function
a theme function

But there is never a case where you can use a mix of these.
So

No, no template file can be implemented as a theme function.
No, you can never use both a theme function and a template, but you can use a preprocess function and a template.