A way to choose a block title's format (HTML tag) What I would like to do is be able to choose what type of Headline HTML element (h2, h3, etc) to use for each block's title. The only way I can find to change a block's Title is in block.tpl.php.  But this forces every block on the site to all have the same Headline.

I've Google'd and searched Drupal.org for a module or manual way to do this but have not found one. Does anyone know of a module that does this?
I know you are asking about D7, but you are missing a key point about templates.  I'd take a gander at http://drupal.org/node/104319 which talks in great detail how D6 does it so you can how it can look at different block templates and then think about whether you need to create a module that has a configuration page for its blocks like what you have above or whether block location is enough.