I'm trying to set up a fullscreen mode with the following code:

// Create the display.
al_set_new_display_flags(ALLEGRO_FULLSCREEN);
al_set_new_display_option(ALLEGRO_COLOR_SIZE, bpp, ALLEGRO_REQUIRE);
ALLEGRO_DISPLAY* dpy = al_create_display(width, height);
if (!dpy) {
  cerr << "\n\nERROR: Couldn't create display!\n";
  return -1;
}

But it seems to work only when bpp is set to 24, and fails for 8 or 16 bits per pixel. I don't know why, since my graphics card supports 8 & 16 bpp modes and I can run games using these modes. (I'm on Linux BTW.)

Also when I try to list available modes with Allegro 5 using this code:

// Get the number of available modes.
int numDisplayModes = al_get_num_display_modes();
cout << "\nThere are " << numDisplayModes << " modes available:";

// List them all.
for (int n = 0; n < numDpyModes; ++n) {
  ALLEGRO_DISPLAY_MODE mode;
  al_get_display_mode(n, &mode);
  cout << "\nMode " << n << ": " << mode.width << 'x' << mode.height
       << ", " << mode.format << " bpp, " << mode.refresh_rate << " Hz";
}

It shows just this:

There are 8 modes available:
Mode 0: 1280x800, 0 bpp, 60 Hz
Mode 1: 1280x720, 0 bpp, 59 Hz
Mode 2: 1152x768, 0 bpp, 59 Hz
Mode 3: 1024x768, 0 bpp, 59 Hz
Mode 4: 800x600, 0 bpp, 59 Hz
Mode 5: 848x480, 0 bpp, 59 Hz
Mode 6: 720x480, 0 bpp, 59 Hz
Mode 7: 640x480, 0 bpp, 59 Hz

which is very strange, since all bpps (formats) are set to 0.

What I do wrong? Why cannot Allegro see my bit depths?

I'm not positive, but some video cards will only accelerate graphics in certain color depths. I used to have an old card with an Intel chip that would only do OpenGL accelerated in 16 bit depth. X11 doesn't "have" 32bpp (although the screen does, but X11 won't admit it) but since it's only the screen it doesn't matter for alpha etc. Maybe Allegro recognizes this and says zero bits per pixel as a default?

Well, when I ask X11 about available bit depths through Xlib's XListDepths function, it shows "24 1 2 4 8 15 16". Also when I use games written for SDL or other similar libraries, they offer non-24-bpp color depths without any problem. So I guess this is something specific to Allegro alone.

What technique does Allegro use to retrieve & change display modes?

I just looked, and al_get_display_mode just doesn't report the format in at all on Linux. That's just a bit embarrassing.

In terms of setting the color depth... Allegro uses OpenGL... do the other games you try also use OpenGL?

Yeah...

Can you tell me the "coordinates" of where is this function definition in the sources? (filename:line). I'd like to take a look at it too.

Some of them, but not all.
I heard that OpenGL can work only with A8R8G8B8 pixels, so it perhaps won't work with 8 bpp, but I also heard that it can work with 16-bit R5G6B5 pixels (though I might be wrong).

But isn't Allegro supposed to be general-purpose graphics library with OpenGL being optional? I remember using some old Allegro version long time ago which wasn't using OpenGL yet, and it offered different color depths and direct access to video memory buffers (it was on Windows back then, though, so I don't know how it applied to Linux).

Suppose I don't need OpenGL, but simple mode switching, double-buffering, and direct access to video framebuffer pixels to draw something procedurally (where 8-bit pixels with color palette are used for performance reasons). Is Allegro still capable of that? Or should I use some other library?

IIRC, this is a limitation of X Windows. On most X Windows implementations, in general, switching color depths is not possible on a per program basis. The whole X server needs to be restarted.

In other words, for your game to be portable, it's better not to ALLEGRO_REQUIRE on the color depth. Don't worry too much about performance Allegro will convert all bitmaps you load after opening the screen to the screen color depth automagically.

Also, Allegro 5 is hardware accellerated so you do need either opengl or direct3d to get decent performance.

There are a few places the function is implemented. For X11, these are:

src/x/xfullscreen.c:332
src/x/xrandr.c:441

Allegro5 only works with OpenGL and Direct3D. OpenGL is only optional on Windows.