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
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.