You could create a template tag function that outputs the appropriate HTML, tailored to whatever the current category is. Then call this tag from any templates where you want the icon with the category name.
The function would be mostly a switch/case structure where each case is a category slug. The subsequent code would echo out the necessary HTML.
Another approach is to identify all functions called by templates to output categories. There are likely filters for these functions that you can hook and insert appropriate HTML into the return values. Your filter callback would also use a switch/case structure much like the template tag idea.
Either concept would be fairly straight forward for existing categories. Things get more complicated when new categories are added and the appropriate icon needs to be associated with the new category. You can add a field to the categories admin screen to accept this input. I’m not sure where the best place is to store this data, but I’m sure a solution is possible.
If the icon to category relationship is stored on a table somewhere, then instead of a switch/case structure, the above mentioned functions would be making a DB query to determine the correct output.