[hill generation, perlin, diamond square] … this kind of algorithms seems suitable when dealing with tile maps that also have a height component but this is not my case.
But it is your case. Mountains are higher than plains, and plains are higher than water.
___/
___/ ___ Mountain cutoff
___/
______/
____/ ___ Water cutoff
__/
You can quantize your data so that if it is between one set of levels, it is counted as one type of tile, whereas when it is in a different range, it is a different type of tile. You’ll be throwing out some detail, but you’ll still get outlines that match the type of noise that you’re generating.
It’ll probably take a good amount of tweaking, and will require you to generate other land features (besides impassible mountains) yourself, but you’ll have to tweak a lot with any content generation solution.