Perlin Noise can be done in 3D just the same as 2D.
Heres a video of it being used with some terrain.
Try making 3d perlin noise as a bunch of block clouds. But remove any blocks below a specific level of noise (the higher the level the smaller and more island like he landmasses would be). It might also be an idea to apply a kind of 3D blur to help prune out small single blocks. Maybe you might want blocks to 'fall' if there is a block within a specific number of blocks below them.
Chances are you want to scale/'flatten' the noise vertically to ensure you get flatter landmasses.
You can overlay several noise's at different resolutions/properties, that allows you to generate some large islands and little ones. Some will merge together too. More noise generations with other thresholds could be used to make different block types. Other another level of noise could forgot the flattening and produce mountains.
Things like trees, water and caves entrances are a bit more tricky since you would need to check to see if they make sense placed where they are(ie trees/caves appear only on top of an island rather than floating in free space).
It might be an idea to look at turning another perlin noise into some kind of probability point distribution, ie a higher value for noise means there is a %10 chance of a tree at that point. Once you have that point you trace down until you find a valid block where you plant the tree provided it meets the conditions required for a tree (ie there is enough space above it. It's on a dirt block, lighting levels, water nearby or whatever.
Of course there are also things like biomes which would be more noise.
Going this route you will want to be sure of of how fast you can produce perlin noise in the numbers you want since you will be making a lot of it. Also find out how much memory it will take, some noise can just be added onto the other noise but other types would require it's own separate overlay.
It might be worth looking and seeing if you can generate the noise using Shaders, OpenCL , DirectX's Compute shaders, or CUDA if possible but if your planning on releasing this commercially you may be limited by what you can use depending on what requirements you want to support. Of course you can produce 2 different generators provided they both use the same algorithm. At the very least you probably want to thread it.
You will also want some flexible noise manipulation functions like blur, stretch, recale values, subnoise.