Welp, you got me started down a really deep rabbit hole… Here’s what I found 
There’s no reason that you can’t use both 2D noise for a heightmap and use 3D noise to determine which cells are solid and which are air. The height map can influence the 3D “density map”. This is probably the best way of making sure you have no floating islands that aren’t connected to the rest of the terrain while still allowing overhangs. At least that’s my preferred method. To get the overhangs you need to somehow offset the input coordinates to your heightmap function. I like to “twirl” them with coherent noise. Yes, this means you’ll use coherent noise to generate the coordinates that you sample coherent noise at. Weird.
Here's a Module for generating fractal (or Perlin?) noise. It's great for making more interesting terrain, with details at different scales.
local r = Random.new(os.time())
function fractalNoiseGenerator(seed, amplitude, frequency, octaves, lacunarity, persistence)
--Generates a noise generator using cohrent noise (math.noise)
--Uses "sensible" default values.
--Check out this glossary: http://libnoise.sourceforge.net/glossary/index.html
local noise = math.noise
local seed = seed or (r:NextInteger(-10e3, 10e3) * math.pi) -- * pi because math.noise is weird at integer coordinates, and pi is irrational
local amplitude = amplitude or 1
local frequency = frequency or 4
local period = 1/frequency
local octaves = octaves or 3
local lacunarity = lacunarity or 1.75
local persistence = persistence or 0.8
return function(x, y, z)
local v = 0
local a = amplitude
local f = frequency
for o = 1, octaves do
v = v + noise(seed + x*f, seed + y*f, seed + z*f) * a
a = a * persistence
f = f * lacunarity
end
return v
end
end
return fractalNoiseGenerator
Here's a script for actually generating the terrain (requires the Fractal noise thing)
local FractalNoise = require(game.ServerStorage.FractalNoise)
local heightmapNoise = FractalNoise(nil, 0.6, 2, 2, nil, nil) --These are just magic numbers
local swirlNoise = FractalNoise(nil, .3, 5, 2) --These are just magic numbers
function mapSet(map, x, y, z, value)
map[x] = map[x] or {}
map[x][y] = map[x][y] or {}
map[x][y][z] = value
end
function mapGet(map, x, y, z)
if map[x] then
if map[x][y] then
return map[x][y][z]
end
end
end
function twirlCoordinates(x, y, z, power)
local power = power or 1
local tX, tY, tZ =
swirlNoise(x, y, z),
swirlNoise(x+1000, y, z), --Don't want the *same* twirl on each axis
swirlNoise(x, y+1000, z)
return x + tX * power, y + tY * power, z + tZ * power
end
function heightMap(x, z)
return heightmapNoise(x, 0, z)
end
function density(x, y, z)
--If you twirl with power 0, you'll just get a plain heightmap
local tX, tY, tZ = twirlCoordinates(x, y, z, 1)
tZ = tZ / (1 + y)
tX = tX / (1 + y)
local densityOffset = 0.5 + heightMap(tX, tZ) - y --Add 0.5 density so that there's a guaranteed bottom layer
return densityOffset
end
function generateTerrain(mapSize)
local densityMap = {}
for x = 1, mapSize do
for y = 1, mapSize/2 do
for z = 1, mapSize do
mapSet(densityMap, x, y, z, density(x/mapSize, y/(mapSize/2), z/mapSize))
end
end
end
for x = 1, mapSize do
for y = 1, mapSize/2 do
for z = 1, mapSize do
local d = mapGet(densityMap, x, y, z)
if d >= 0 then
local block = script.Block:Clone()
block.CFrame = CFrame.new(x, y, z)
block.Color = Color3.fromHSV(((y/mapSize)%1), .75, 1 - (y/mapSize))
block.Parent = game.Workspace
end
end
end
end
end
generateTerrain(64)
Here's a simplified terrain generation script, to see how 3D noise can be used to make a "height map".
local FractalNoise = require(game.ServerStorage.FractalNoise)
local heightmapNoise = FractalNoise(nil, 0.6, 2, 2, nil, nil) --These are just magic numbers
function mapSet(map, x, y, z, value)
map[x] = map[x] or {}
map[x][y] = map[x][y] or {}
map[x][y][z] = value
end
function mapGet(map, x, y, z)
if map[x] then
if map[x][y] then
return map[x][y][z]
end
end
end
function heightMap(x, z)
return heightmapNoise(x, 0, z)
end
function density(x, y, z)
local densityOffset = 0.5 + heightMap(x, z) - y --Add 0.5 density so that there's a guaranteed bottom layer
return densityOffset
end
function generateTerrain(mapSize)
local densityMap = {}
for x = 1, mapSize do
for y = 1, mapSize/2 do
for z = 1, mapSize do
mapSet(densityMap, x, y, z, density(x/mapSize, y/(mapSize/2), z/mapSize))
end
end
end
for x = 1, mapSize do
for y = 1, mapSize/2 do
for z = 1, mapSize do
local d = mapGet(densityMap, x, y, z)
if d >= 0 then
local block = script.Block:Clone()
block.CFrame = CFrame.new(x, y, z)
block.Color = Color3.fromHSV(((y/mapSize)%1), .75, 1 - (y/mapSize))
block.Parent = game.Workspace
end
end
end
end
end
generateTerrain(64)
Here is a (huge) picture gallery of stuff I found out when playing around :P
Toothpaste series
Basic examples of combining height maps and twirled coordinates. Nice overhangs, no floaties.
“Fire” series
Because I picked some cool colors and the shapes look like licking flames \m/. Examples of extreme amounts of twirl (the “bases” of the “mountains” are horizontally far away from their “peaks”).
Rainbow series
Experiment with twirling more at the top, and less and less towards the bottom. Extreme twirl can generate really nice caves, but reducing twirl near the bottom of the world prevents them from going too deep.
Various
This one colors blocks depending on the “density” at their position, instead of their height. I don’t have anything clever to say about this :
Here’s a 2D version of many of the same concepts. Instead of using coherent noise for the height, a simple sine curve is used. The X coordinate is still twirled, giving it overhangs. Using a sine curve instead of a noisy heightmap gives a better understanding of what exactly “twirling” the coordinates does (there are regular peaks and valleys, with consistent heights and depths. The noise is only used for “surface level” features). Also it looks like fire 
Here’s a cartoony version of the same thing. The sine of the y coordinate is used for twirling the input to math.noise(), which is kind of the opposite of the other flames. Any coherent function can be used to “twirl” the coordinates. I’m really interested in what other examples of smoothly varying functions I can find.
Just a heads up you can still totally get floaties, but only if you twirl too hard. You’ll have to tune your specific parameters to your needs.
Hope this rambly post is some help, and let me know if you have questions 