As you said, you could just build a bunch of levels yourself and randomly pick one. But that's not really random generation.

Instead you would have to think of the game as components and test them to make sure the level is not impossible. Probably starting with the ground. If you had truly random ground for a Mario game then there is a good chance you would end up with an impossible level because there might be a gap that is larger than Mario can jump. That means you have to put limitations on how random your ground can be (never make a gap bigger than Mario can jump). In the case of a game where you have a top down view and are navigating something like a maze you would have to build a maze that is traversable.

You also have to make sure you don't run into impossible situations with enemies. If (randomly) 20 enemies appear when you get to a certain point of the level in a Mario game, you'd probably lose. Likewise for a game like Diablo enemies would have to have rules on where they can spawn and how many of some difficulty to kill can spawn there.

In a game like Mario the goal is simple, get to the rightmost side of the screen without dying. For other games that might not be so simple, you might have to invent rules for what the winning condition is.

Try to think of a more specific game that you would want to make and worry about random generation for that particular game. Random generation in general is... well, very general.