An easy solution for this is to leave the original tag as a synonym of the new one when "renaming". Links should silently redirect when this is done. And you can do this now!
Summary of rambling that follows
Let's say I tell some friends to meet me at my house later on today, and then find out I need to leave early. I have two choices:
Never leave (perhaps get someone else to leave for me). As a permanent resident, I'm easy to find.
Tack a note on the door before I leave, instructing them to meet me somewhere else.
I rather prefer the note.
Let's talk about permalinks
I assume by "permalink", you're envisioning a system where a tag has some sort of ID number, which remains consistent regardless of the "name"... While tags certainly do have numbers associated with them internally, those numbers are considerably less "permanent" than the names themselves, and one name may have many numbers over time - indeed, the name is about the only remotely permanent thing you could possibly have for a tag! Remember, there's actually no "rename" function within the system right now; individuals can retag a question, replacing one or more tags with one or more other tags, and moderators can merge tags, automatically replacing one with another on all questions where the former appears... But neither one of these actually mutates the original tag.
If you think about it, "renaming" would be a very strange feature to have - you could end up with two completely different tags that happened to look identical!
Now, imagine for a second if every time a new tag were created an associated number was also created, and the system faithfully preserved this pairing for all time (permatags). In order for this to be useful, you'd want to make merging automatically associate the number of the old tag with the name of the new one (while keeping the association with the original name as well, lest the tag accidentally be re-created with a different number and thus rendered impermanent) - now you have a many-to-many relationship between names and permanent numbers.
Ok, so that's complex as hell compared to our current system. But would it work?
No, I'm afraid it doesn't. Let's say I permalinked to [georgia], before someone realized that the tag is ambiguous and merged it into [georgia-country]. My permalink still works, right? Afraid not - see, I was intending to link to my favorite collection of Peach State questions, and now that is forever broken because the questions related to [georgia-usa] had to be retagged, their association with my poor permalink forever lost.
...In other words, after all that complexification, we're still stuck with the same problem that exists today with using synonyms. Because the "number" is really just another synonym, albeit one created automatically by the system.
Might as well just stick with what we've already got.