"Real time" is a subjective term that depends completely on the hardware you're running on. Speaking from experience, timely chunk generation is one of the primary reasons MineCraft Pocket Edition would be substantially different from MineCraft PC. You say that,
chunks to be 3600 tiles high, and changing the size to be 16x(16x)3600 runs very slowly.
It would, because you're no longer playing nicely with either cache line sizes or cache level sizes for run-of-the-mill consumer processors. Let's assume a simplistic architecture where there is only one level of cache, L1. If L1 has a total size of 32kb x 8 ways = 512kb, and your 16x16x3600 assumes just one byte per voxel, that is already 900kb per chunk, which means your cache is going to miss at least once (actually, more) and you will experience a lengthy pipeline stall as the data is fetched from the heap / main memory. If 10 bytes per voxel, then you will have many more cache misses in constructing the mesh for a single chunk - not to mention cache misses on game logic, physics etc.
Every cache miss means a call out to main memory (in this simplistic, one-level cache example) and instigates the loss of hundreds of CPU cycles where program thread is doing nothing but waiting for that data. This is known as a pipeline stall.
But that's not all. Treating surface terrain as a 3D grid is, as you suggest with your question about 65536 cubes, a fairly naive idea. Ideally you want to be doing 2D heightmap generation, not 3D grid generation, on the surface of your world, say e.g. 16x16x(32-bit float). This leads to exactly 1 kb per heightmap chunk. You could even use 64x64xfloat or what have you, as then each of these is still reasonably small and fits an L1 cache way. You could alternatively opt for octrees or KD-trees.
Once you get it working with heightmaps, then you can expand the solution to deal selectively with small sections of overhang where you use regular 3D grids, i.e. said grids override the underlying height map in terms of rendering and game logic. This allows for e.g. cave entrances at surface.
P.S. There is more to it than this. You need to be using a single array of struct for each of your chunks, and never an array of class / objects, at least in higher level languages like Java and C#, because with class instances you have no control over where they allocated, whereas with struct arrays, all array elements are allocated contiguously in memory, because structs are a value type.