so lets say, its gonna be a tiled map
there is a few ways that I know of to do this
each tile or block, is going to have a bodydef associated with it, keep a Bag Array or something of all of those bodydefs
have it iterate over the array, checking to see if those bodies/tiles are beyond lets say x < -1000, then world.remove(thatBodyDef);
Have a giant box/line/whatever to the lefto f the screen x = -1000, and then setup a custom collision event, whenever a tile collides with it, remove that tile from the world
Have a 'chunk' each chunk contains lets say 50x50 tiles or whatever. This way you aren't checking against hundreds or thousands of blocks x position. Youd just check against 3-10 chunks position. When the chunk is far enough gone to the left, remove the chunk(and all of its tiles that exist in that chunk)
And on the opposite side of things.
On the positive x > 1000, you could do almost the exact reverse of the above #1 or #3, either have a chunk system constantly cycling through chunks or create a single column of block/tiles/boxes much more frequently.
For 'randomized level' depends on what style of dynamic you want. You could use Simplex or Perlin noise. Or you could use a 'walking/roughness/windiness' algorithm (http://roguebasin.roguelikedevelopment.org/index.php?title=Basic_directional_dungeon_generation
) Like that, but instead of up/down, implement it to left/right
There are several other ways to handle it, but thats what I would recommend
Recently I implemented the dynamic level, being randomly created in real time, infinite to the right, using box2d.http://www.java-gaming.org/topics/escape-copter/30493/msg/281645/view.html#msg281645
play the .jar and see how it is.
Then you can also look at my sloppy way of implementing ithttps://github.com/namrog84/ColorCopterGame/blob/master/CopterGame/src/com/newrog/coptergame/Chunk.javahttps://github.com/namrog84/ColorCopterGame/blob/master/CopterGame/src/com/newrog/colorcopter/entities/Block.java
The chunk and the block is whats handling most of whats related to your question.
p.s. If you decide to dive into the code at all, be mindful it was written hastily and poorly. There are some 'unused' things and some 'poor approaches' to several things, However it does work and is functional, and its performance was just fine for what I needed, so I never cleaned it up