How do I do AI pathfinding in a scene that changes drastically during play

My current project/experiment will involve an in-game level building system that is grid/block based. So parts of the level will be built during gameplay, by the player. But there will be AI entities that need to be able to navigate those new sections of the level.

I am aware that I cannot regenerate the Unity navmesh at runtime. And, unless I have read wrong, I cannot regenerate the A* Pathfinding Project navmesh at runtime. I also don't think I want to use a purely grid based pathfinding system for the AI's as it would not look very natural in this context.

So what are my options for AI navigation of a dynamic scene that will have massive changes during gameplay?