Adding ASCII characters to HTML links in Drupal
You can use the Menu HTML module for that.

It uses a bunch of alter hooks, which means you could theoretically reproduce the same functionality in a theme if you really want to. So yes, it's possible to solve without using a module per se.

Modules are the proper way to add such functionality, though, hacking this into a theme is bad application design in my opinion. Drupal is, intentionally, a modular system; don't be scared of installing modules to add functionality, that's what you're supposed to do :)