Implementing a Large RAM on Cyclone II - is it possible?

So, 2 writes at most at any single time?

Sounds like you should be able to format it as 16 sub-arrays of width 1 and depth 4096, by combining up to 64 columns in each sub-array, and fit each in one M4K.

The synthesizer is generally pretty good at inferring memory blocks, so, as long as your access pattern is recognized as something it should be able to implement in RAM, it'll usually do it for you. If it fails, you'll know it because it'll put everything into logic cells instead, and you don't have enough logic cells for that, so it'll end up being unable to fit the design.

If you can't coax it into doing M4Ks for you, instantiate a bunch of altsyncram blocks instead using the IP editor. Not necessary to go down to coding all details of selection circuitry.