I want to record video from games, therefore I cannot use very large video resolution, ...
Why are you so certain about this? I can record Full HD so I don't see why you couldn't.
Make sure you are using the right tool to do the job, I would recommend XSplit which can record to file.
I tried to use YouTube's recommended 854x640 resolution, ...
Why are you trying such low resolutions? That won't look sharp at 1920x1080 which is of double size.
but it wasn't possible with h264 and the encoding software I used (Handbrake) converted it to a width of the nearest multiple of 4, ...
YouTube lists 854x480 which is 16:9, I don't see where you got 854x640 from which is 4:3.
which I think is a limitation of the h264 format.
Formats don't limit the resolution and scaling you use. If I want 1000x10 with a 100:1 ratio for a big banner board somewhere along the road, I am able to use h264 for that.
The video I encoded was sharp and fine quality, but when I uploaded it to YouTube, it lost a lot of quality and the preferred large video view looks almost as bad as a 320p video. I tried to wait a few days but it never got sharper (in case it didn't process it completely yet).
How lower the resolution goes, how more noticeable the compression gets.
So, which resolution and encoding options I should use, if I want the large video player to have the sharpest possible video, retaining the original video quality as good as possible?
1920x1080, with the highest FPS and bit rate settings possible.
It's as simple as that: The higher resolution you go, the higher quality your video will look.
I noticed that recording with 640x480, the video was sharper than with 1280x720, so I'm not sure what im doing wrong here; both were h264.
While this sounds odd, I think it has to do with that the former is 4:3 while the latter is 16:9. Perhaps one of them gets scaled? In any case, this has something to do with the video files, not YouTube. Unless you are comparing them both on 360p, because then the lower resolution would undergo less compression.
Is it anyhow possible to prevent YouTube from re-encoding the videos?
Nope, that's the way the content model works. Fit every device...
I just wonder how people can make so sharp videos, while mine are all blurry after upload, but before upload they looked fine. I also tried YouTube's suggested bitrates with h264, but it didn't work any better.
It is the resolution that matters, by limiting yourself from the start, you are stepping on your own toes.
So, ditch the recorder you are using now and check out other ones (like XSplit above). If your computer doesn't support them, then you might benefit better equipment.
I haven't started casting or spent more time to up my live casting settings, but here is an example of 720 casting quality, note that this is limited by my network (or I'm just uncertain how high I could go) and not by my recording capabilities. So, if I were to save to a file and upload that file it would be of much higher quality, but I don't have the software installed at the moment to try...