We are in the first stages of making a 2D game at the moment, which will focus on destructible environments and objects.
However, we have already encountered serious problems with the choice of the right graphics API
At the moment, we use SDL - but the problem we see with it is that it isn't really performant, and has no hardware-accelerated surface scaling and rotating! - This also makes animated camera zooms practically impossible
We have thought about using OpenGL as well, however the problem we see with it is the direct pixel access that we need. Do you think it would be the right choice?
What we are searching for is a graphics API that is hardware accelerated, offers direct pixel access and modifying as well as fast blitting, rotating and scaling of surfaces
Cortex Command is already doing a lot of what you're thinking of doing, they use Allegro - but it's not hardware accelerated. You can get access to the pixels in OpenGL objects and DirectX textures, you wouldn't want to do it too often though as it's not necessarily cheap to copy stuff back and forth from graphics ram to main memory.
You might be able to minimise how often you manipulate the pixels then. For 2D APIs I'm personally quite fond of HGE, but it's DirectX based.
Maybe have a look at SFML.
From the features list:
OpenGL can give you direct pixel access, but its sometimes difficult to understand why it doesn't with some functionality...
glDrawPixels is probably the simplest and most reliable way - you can copy a block of pixels from "regular" memory on to the framebuffer - this isn't especially fast, but its old (its documented by MSDN its so old), well supported across platforms (and hardware) and gives you total control and accuracy for pixel rendering - you can even program all of your rendering logic to run on the CPU and just use it for drawing pixels. However, it is probably sensible to try and leverage the performance benefits of using the hardware...
Using the hardware is fine, but having pixel-perfect precision is not guaranteed for even the simplest of operations - often the driver will do something a little different to what you are expecting - GL_LINES, GL_LINE_LOOP etc. usually show this best - its difficult to use them with pixel accuracy and as far as I know there is no way to have them render consistently if you want thicker lines - different drivers will do different things. Although it might only be a single pixel difference I know that can often be enough to cause a problem.
Some operations however are very likely to be pixel-perfect, for instance, sampling a texture across a screen-sized quad. This is vital for deferred rendering and similar techniques where full-screen buffers need to be composited somehow - so long as you avoid the common problems with rounding errors you can normally position triangles/quads with pixel perfect precision - just don't iterate around the screen by accumulating floating point values - make it as simple as possible by using a transform which has integer values for each pixel, this can be achieved with the glOrtho function. In fact as a rule of thumb the triangle rendering methods get the most attention and need to be the most consistent simply because the most popular graphics software (games) are totally dependent on them.
If you are struggling to find ways to do particular operations then consider looking into shaders as well - they are almost always sufficient for whatever you want to do (although it might be challenging to make it performant) and give you that extra level of control that you are likely to need for a high quality 2d renderer.