Finally I have what I was searching for. This time it is an LCD 64128A LED module by Reichelt for 16.70 EUR.
I followed the instructions in the playground Arduino Playground - GLCDks0108 and it worked immediately with Pinout B.
It is not a shield but by now I have a Boarduino, so this is acceptable. Speed of the benchmark is about 5 FPS. Not really great (I would have prefered >10FPS) but sufficient.
However it uses up a lot of pins. Seems I will have to order a Sanguino or to design my own Sanguino clone to fix this 