Best practice for creating a custom archive template for a custom taxonomy which works on all themes?

Creating pages is the job of a theme, plugins should not attempt to do that. What you can do is to provide a shortcode which will add the relevant html when used and let the user add it as part of his content however he wants to use it.

That said, if you really must have something automatic you can use the page.php template of the active theme and supply your own content by using the the_content and the_title filters. This should work for most themes with a simple page design.