How to make pathfinding over Minecraft-style terrain in Unity?

Unity offers a solution for a baked navigation mesh with static 3d objects. I need to have a way to pathfind over a mesh that is dynamically altered in runtime and therefore cannot be pre-baked. I would also like to have the support for obstacles that are not blocks (such as stuff like trees and rocks on top of terrain).

The Mesh in question represents a Minecraft like terrain, best thought of as being made up of addable-removable blocks, but only incorporating the visible sides of those blocks in actual mesh. Currently, the algorithm is capable of altering a 3d mesh based on its vertices and triangles alone (i don't need to store any other data, as long as the data within the mesh itself is properly sorted), but i do still need to rebuild the entire mesh for every cube i add or remove (so it is not going to happen very often).

So, basically, what i have is a 3d mesh that can be altered in runtime by adding and removing vertices and triangles to represent adding and removing visible cube faces. Currently, every face is represented with 4 vertices and 2 triangles, but i plan to optimize it further so that i'm able to reduce the amount of vertices and triangles to represent large flat surfaces.

I haven't tried any actual pathfinding solutions yet. Trying to figure out what kind of approach would work best for the problem.

What i want is to have agents pathing over a mesh that can be dynamically altered, while taking into considerations the limitations of configurable speed as well as jump-up and fall-down distances. A solution that specifically relies on the mesh representing series of imaginary cubes of different types would be alright, but if a more general solution is available, then that's what i'd prefer.