From what I understand of your question, you are trying to figure out how to make a navmesh out of a tile-/grid-based terrain.
Well in fact, tiles/grids are inherently easier to work with, and one way or another you are going to have to apply A*, but you can apply it just as easily to a grid as you can to a navmesh. The point being that A*, like any graph search algorithm, operates on graphs. A navmesh is a graph, and so is a tile grid (although more densely and regularly connected).
I'd suggest that you simply focus on doing pathfinding in a grid, unless you believe there is some substantial gain to be had by using a navmesh (I don't).
And if you do, then a possible way is to generate a navmesh first, then rasterise its polygons by filling them in with tiles of different types (you'd use point-in-polygon checks for this). Now you'd have a tile based world, but you'd also have a nice navmesh already present and in agreement with the tiles. It's harder to do this the other way around, IMO (produce navmesh from tiles, which I think you are suggesting). Caveat: The problem here is, well, creating a planar navmesh graph. Not really that easy, I'm afraid, unless you have some ideas of your own. The graph planarity problem is one of the hardest problems in computer science. Hence: Use a grid.
EDIT I am guessing (I have to guess a lot here!) that the reason you might prefer a navmesh over a grid is because you want creatures / objects to be placed or to roam "pixel-freely" rather than snapping to grid cells. Well I would still recommend sticking with the grid, but maybe flood-filling certain areas with a code to say, "this is zone 1", "this is zone 2" etc. That way you can limit your entities to ranging about in a given zone. To remove the aliasing effect of a grid, you can also introduce minor variations to the centre point of each tile, so that it looks less regular when you entities move. Just a thought.