You can build a tag menu using
wp_tag_cloud() or if you don't like the cloud thing, build a menu from the return from
get_tags(). Of course this does not consider the current category. In order for your permalinks to accept both tag and category parameters, you would need to use the Rewrite API to set it up. However, if you use the traditional URL parameter form, you can build a combined tag and category_name link and it will work as expected, though the category archive is used, it is limited by the tag parameters as well.
So you need to alter the tag link hrefs to look something like this:
You can get the current category from the global $wp_query object.