As it has been previously remarked in the comments, and as you seem to think as well, random generation is a just another possible form of procedural generation.

Procedural content generation implies that content is being generated by an algorithm rather than manually crafted by a human being. That said, the frontier is very blurry. On one hand, we have what we could call full-blown procedural generation, such as in Minecraft or No man's sky. On the other hand we have fully-designed games such as, perhaps, Mario and other old school titles. However, there is a lot of ground in the middle, from simple design-time tools for laying out textures, passing through the offline creation of, for instance, trees, landscape and even multitudes, to the online generation of maps in Civilization, or items and monsters in most RPG titles.

Each and every of these examples could use a mix of random and deterministic techniques. Like @Philipp suggested in the comments, generation can be completely deterministic and used just for the sake of compression, like the classic Elite game. In the other corner, it can be (almost) completely random, like many puzzle games (as long as they are solvable, so I guess completely random is mostly out of question). Most of the solutions sit somewhere in the middle, using a set of deterministic rules that can be randomly applied in different orders, or with various inputs, much like your own examples.

There is also a growing field named search-based procedural content generation that approaches content generation as an optimization or search process, and often employs a random generator coupled with some heuristic optimizer (like GAs, or other evolutionary algorithms) and a fitness function that determines the "goodness" of the content. This has the advantage that we don't need to know how to generate good content, we just need to know how to generate lots of content, and how to grade a content's quality (which could be as hard as actually generating it, but it is often easier).

So, to round up my answer, I think that random generation can be mostly seen as a (many times simple) form of procedural generation, and also as component of many procedural generation algorithms, but there is also a lot of procedural generation that is mainly non-random.

Much more info can be found of the PCG wiki.

As it has been previously remarked in the comments, and as you seem to think as well, random generation is a just another possible form of procedural generation.

Procedural content generation implies that content is being generated by an algorithm rather than manually crafted by a human being. That said, the frontier is very blurry. On one hand, we have what we could call full-blown procedural generation, such as in Minecraft, Terraria, Starbound or No man's sky. On the other hand we have fully-designed games such as, perhaps, Mario and other old school titles. However, there is a lot of ground in the middle, from simple design-time tools for laying out textures, passing through the offline creation of, for instance, trees, landscape and even multitudes, to the online generation of maps in Civilization, or items and monsters in most RPG titles.

Each and every of these examples could use a mix of random and deterministic techniques. Like @Philipp suggested in the comments, generation can be completely deterministic and used just for the sake of compression, like the classic Elite game. In the other corner, it can be (almost) completely random, like many puzzle games (as long as they are solvable, so I guess completely random is mostly out of question). Most of the solutions sit somewhere in the middle, using a set of deterministic rules that can be randomly applied in different orders, or with various inputs, much like your own examples.

There is also a growing field named search-based procedural content generation that approaches content generation as an optimization or search process, and often employs a random generator coupled with some heuristic optimizer (like GAs, or other evolutionary algorithms) and a fitness function that determines the "goodness" of the content. This has the advantage that we don't need to know how to generate good content, we just need to know how to generate lots of content, and how to grade a content's quality (which could be as hard as actually generating it, but it is often easier).

So, to round up my answer, I think that random generation can be mostly seen as a (many times simple) form of procedural generation, and also as component of many procedural generation algorithms, but there is also a lot of procedural generation that is mainly non-random.

Much more info can be found of the PCG wiki.