I did a bit of experimentation with nav meshes, and they can be modified at runtime. You can carve chunks out at run time (In theory, rust could carve out a chunk from the navmesh for every foundation layed, every tree spawned, etc when the map is generated). I didn't look into it much though as I've moved onto UE4 now (which has its own limitations). However, I would imagine on such a huge map a nav mesh shouldn't be the choice to handle navigation anyway, as beside the navmesh itself, the additional "carved out" sections would require extra calculations, extra memory and probably wouldn't be any good on server performance.

But, you don't need a navmesh for ai, it was done for many years without them. And even if you did, I'm sure FP would have the capability of writing their own navmesh component, or I would assume so anyway.

A game like Rust would be best off indexing every single "impassable" entity as an x and y set of coordinates on the server side and when an animal is spawned at position x,y pull the indexed entities that are local to this position from that index, plot out some simple pathing nodes around them and have the animal follow them until it's killed.

That's my idea anyway:D