UFO: Alien Invasion
UFO: Alien Invasion is an open-source X-Com-like that’s been in development for quite some time (and is one of the relatively few big open-source game projects that’s been playable for years). While it’s use of a heavily modified Quake 2 engine as a base has imposed a few feature restrictions, random maps are definitely supported.
While the game world still has the concept of tiles, the large building blocks are actually constructed in a custom version of the Radiant map editor, and assembled dynamically in the game. Together with some fixed maps, this gives the game a fair amount of flexibility in the individual map layout, with regional variations in terrain and architecture, as is appropriate for a globe-spanning X-Com-like.