How do I navmesh when my height values for my terrain are given by a perlin noise function and my other meshes are also possibly placed by a random or noise function? Can I still use the nav mesh or do I have to make my own dynamic pathing tools?
Own tool or asset store, there are a few decent ones. I think "they" are planning for runtime navmesh baking.
You could do something like converting the heightmesh to a navmesh and move it up slightly, but I would just use an asset from the asset store. I always recommend the A* project made by Aron Granberg. I haven't really tested the navmesh options in the pro version, but an A* pathfinding system would be very easy to implement and update in this sort of sitaution.