Whether your attribute is (part of) a key or not has nothing to do with the issue.
You have issues of character set conversion with ANY data traffic to/from this attribute anyway, regardless of whether it's a key or not.
Yes, in order to encode "correctly", and have the best possible guarantee that your data will never get corrupted because of character set conversion issues, you need the Unicode character set and one of its encodings.
I do have some serious doubts about the table itself, incidentally. What do you do with Heidelberg, Germany and Heidelberg, South Africa ? Oxford, UK and Oxford, US, where there's even hardly a state without one ?
What kind of information depends on that key ? If there is none at all, then your table is more of a "variable type" than it is a "genuine table". In that case, you might just as well forget the table and make your cityname attributes just plain String.
If you are really required to produce some "canonical spellings" for citynames when exporting data from the database, then I'd advise to try and set up a "phonetic search table" in which "commonly used spellings" are linked to the "canonical spelling" you are required to produce. Expect a serious effort in getting such tables populated, however.
In that case, then in addition to the already mentioned München/Muenchen and Western/Greek alphabet issues, don't forget about the Liège/Luik/Lüttich (München/Munich) kind of issues.