Rebinding keys is the first thing I do when I start up a game for the first time. Usually there's a bit of tweaking to be done afterwards as you learn what each action actually does, but ideally I like to clearly define and learn the controls before I even start a new game.
I've got a very specific set of controls that I try to use with pretty much every game (in first or third-person games I always use WASD for movement, C for crouch, Space for jump, Shift for walk/run, R for reload...), and I modify it based on what you can actually do in the game and what feels natural. For example, the "use" key can be either E, F or RMB depending on what exactly it does and whether the game has stuff like leaning in it, in which case Q and E would be reserved for that. I've also got used to setting up many of my keys alphabetically, meaning that I use M for map, J for journal, I for inventory, H for holstering weapons, G for throwing grenades, and so on, which is easy to remember, allows you to access all the critical keys (like C, R and G) even in the middle of combat, leaves some room for mapping additional combat abilities into the vicinity of WASD if the game has them, and is often quite close to how the default controls are set up. However, if the game has a journal/briefing screen but no separate inventory and map screens, I always use Tab instead.
Not being able to rebind keys is a crime, plain and simple. The only cases where I can somehow tolerate it are when the control scheme is so unusual that using your preferred bindings wouldn't really even work, like the aforementioned Gothic 1, but I'm only giving G1 a pass because it's such a good game in other ways.