I'm ssh-ing to a server several thousands kilometers away, and every keystroke takes 500-800ms, so it is getting annoying.
Is it possible to have my ssh client cache each line I type locally and only send to the other server when I press return?
See the Compression (-C) option in man 1 ssh. It may help on your circumstance.
A better question would be "What's the round-trip latency of my connection?," which you can determine by looking at the round-trip time (RTT) via ping. Take a close look at the -s, -M, and -U options (see man 8 ping) to enable you to adjust your packets to see if the problem is dropped packets, or some other aspect of your network connection.
Distance can certainly play a factor on certain types of networks (DSL or satellite, for example) but has much more to do with network type, network congestion, and other factors that you haven't mentioned in your post.
Lastly, don't discount server or host issues. Try testing your connection against various servers to see if you have a problem that's limited to a single host, or if your issue is more generic.