I want my game to be able to generate a random map every game, is there a way to genereate a random terrain on the fly?
Yes, you can generate random terrain on the fly in Unity! (You have to code the logic for it yourself though.)
If you mean terrains specifically, see the Terrain class, which you can use to read and write heights of the terrain, and the other terrain data. You can also look at the Terrain Toolkit by Sandor Moldan - though I haven't tried it myself, it has a runtime API which can probably be used for creating random terrains at runtime.
If you mean "maps" in general, consisting of various models etc., then you can do that as well. One way to generate random maps using models is to make models that can be assembled in many different ways, like LEGO bricks. You can then create a random map by assembling the existing pieces in a random way. Also have a look at this random maze generator.
If you want an even more freeform map that is not made of pre-existing pieces, you can also generate meshes on the fly. For getting started with creating procedural meshes, see the Procedural Examples demo project.