I vote for 4, since the user already uses cookies and already has that value. Also it's 2012 - what does "There are obvious problems if a user doesn't use JavaScript." even mean? If they use noscript or something similar, then they won't see "hi xxx", unless they whitelist you. That's pretty much it. (also for most pages, there will be more issues than just the greeting)

1 and 2 work fine if you're doing the caching. Exporting that kind of caching to CDNs may be a bit more tricky (not impossible though...)