Qualities (Genuine, Unusual, Strange, etc.) are independent of modifications made by tools such as paint and name tags and cannot ever be changed. (Unless you count the Strange Bacon Grease, which probably takes away the original item and gives a strange one.)
If you rename an item, the name will still be displayed in the color for its quality, but the quality will not be added to the name you choose. For example, if you rename your “Genuine Ham Shank” to “Squishy Club”, its name will not be “Genuine Squishy Club”, but just “Squishy Club” (in green text).
Notably, renamed Strange items do not change their name as they rank up (the rank is instead displayed as a subtitle under the name).
For an example, here's my renamed Vintage Flare Gun in TF2's backpack view (with quality colors turned on):