I really don't think Salesforce is going to be able to do this for you. In order to auto-translate Salesforce would need something from the user to determine the language. In the event of a public site, the user record as you have determined is inaccurate/not useful and this is the only information I imagine Salesforce will be able to reliably use.
There's only two ways I can think to auto-translate the values and they both require information from the browser. One is to detect the user's location the other is to detect the user's language. I'd go straight to option 2 as it's likely more consistent (and less likely to raise security concerns. have you ever seen the "this website wants to know your location" warning in chrome?).
JavaScript translation options - This references the Google Translate API which allows you to translate without hardcoding values. The other options require hardcoding.
For the lazy people out there:
It's up to you to decide if you want to fight the fight but you could also argue that the site should not be public (requires registration) so that you have a user record for each person. Use the language issue as an example. Many stakeholder's/executives don't know Salesforce at a technical level making them easy to manipulate. Considering the fact that option 1 exists I'd avoid this
For the insane people out there:
If you want to get CRAZY you can try to dynamically set the public user's language or something but this will result in some really wacky behavior. You'd have to set it before every call to the database and that is still not guaranteed to work as a few calls could over lap resulting in users seeing the wrong language or a "unable to lock row" error. The latter you could catch in a try and (dear god don't do this) loop until it succeeds. If you have a low traffic site this might not be too crazy, but still... don't do it.