The other answer is incomplete, so I'm adding a few points to it.
Finally, keep in mind that Random Battles has a subjective leveling system that is vaguely based on tiering and Random Battles win rates, so some Pokémon that are low-tier in tiered formats can be actually quite useful here. For example, Bellossom will only dream of going higher than PU, but its combination of Quiver Dance and Strength Sap alongside its high level makes it objectively one of the biggest threats in Random Battles. Basically, don't always discount low-tier Pokémon, and don't expect all Uber and legendary Pokémon to be your wincons!
Source
Rather than only making up for the tier differences, it's based on Random Battle win rates, and marginally on tiering. For example, a Pokémon such as Spinda, which is (was) Untiered, should technically be one of the best Pokémon in Random Battles because of its tier, but that is not the case. Spinda can not win battles singlehandedly; it's much more of a deadweight as its stats are horrible and it's usually a momentum drain for any team. But, on the other hand, a Pokémon such as Drapion, which is also NU by tiering, is a great offensive threat in Random Battles because of its extensive movepool + options such as Swords Dance, and defensive sets which incorporate Toxic Spikes, too.
The Pokémon are also level-balanced, with the strongest Ubers Pokémon placed at level 70 and the weakest fully evolved Pokémon at level 99. Most OU Pokémon are level 74, UU 78, RU 82, and NU 86.
Source
Now this is somewhat inclined towards tiering. It's outdated though; chances of getting extremely bad Level 99 Pokémon (such as Poliwag) are exceedingly low now, as it was an irritant between players as even with the higher level these couldn't really do anything significant.
Anyways, if a NU Pokémon is very good in Random Battles, it would not remain at Level 86. It's Level would be scaled down to something near ~80. So win rates + initial tiering would, usually, decide about a Pokémon's level in Random Battles.
Please keep in mind that whatever I've said in this applies only to non-Battle Factory and non-Super Staff (4, Bros Brawl) Random Battle metagames. Battle Factory has Level 100 Pokémon of a single tier so that the playing field is levelled in both sides, and Super Staff battles have Pokémon which are, again, Level 100, but with custom changes so as to better the playing environment and the metagame.
Hope it helped.
