Well, mainly, the same way we did it before exceptions existed - the old "check the return value approach". If an allocator doesn't use exceptions, it will usually return
null when an allocation fails. A well written game will check for that and handle the situation in whatever way is safe. Sometimes, this means terminating the game (e.g.
std::terminate) or at least reverting to last known safe state (e.g. when you allocate from a pool, you can safely dispose of the whole pool even when it's in an unsafe state).
Many games do use exceptions for cases like this even then. When someone says "avoid using exceptions in game code", what they usually mean is "only use exceptions for truly exceptional cases, not for mundane flow control". The setup for catching an out of memory exception is cheap - the cost is mostly in the throw, and the complications you get with handling the exception. Neither of those is very important in a typical out of memory case - you almost always want to terminate anyway.
Mind you, most games will just crash. This isn't as crazy as it sounds - you usually have some memory usage as a target, and make sure your game doesn't reach that limit (for example, by using a unit count limit in an RTS game, or by limiting the amount of enemies in a section of an FPS). Even if you don't, you usually don't run out of memory on any reasonably modern system - you run out of virtual address space (in a 32-bit application) or the stack, for example. The OS already pretends that you have as much memory as you ask for - that's one of the abstractions virtual memory provides. The point is, just because you have 256 MiB of physical RAM doesn't mean that your application can't use 4 GiB of memory. Some games might not even mind too much that all of their data isn't in physical RAM all the time (as long as the application doesn't need to touch that data, it can stay on disk, for example).