I'm trying to generate an infinite map, as such. I'm doing this in Python, and I can't get the noise libraries to correctly work (they don't seem to ever find my VS2010, and doing it in raw Python would be way too slow). As such, I'm trying to use the Diamond-Square Algorithm.

Would it be possible, in some way, to make this technically infinite?

If not, should I just go back to attempting to get one of the Python noise bindings to work?

This can be done. Divide up your landscape into "tiles", and apply the midpoint displacement algorithm (as I prefer to call it) within each tile.

Each tile must be big enough so that the height at one corner does not significantly depend on the height in another. In that way, you can create and destroy tiles on the fly, setting the height at newly appearing corners to an independent random value.

That value (and the randomness within the tile as well) must be seeded from the tile's position, so that you get the same tile each time.