Ubuntu – Downgrade a bunch of packages

I still cannot find packages of linux-image 3.2 by apt-cache search linux-images*. Where I am wrong?

On spelling. The correct command is

apt-cache policy linux-image-*

Also, the Tab Completion feature is very handy and you should learn to use it. Open a terminal and write

 sudo apt-get install linux-image- 

Then hit Tab key twice and read the list, can you see 3.2 kernel ?

do I need to install linux-header package too, are there more package I should install?

Every linux-image has its own linux-headers version, so it is preferable to install them too.

sudo apt-get install linux-headers- 

and use the same Tab Completion feature (as in linux-image- above) to locate the appropriate ones.

I never played with this before, but I would suggest that you hold (or lock) the version of the dependencies that cause you trouble. This way apt has a more limited number of possible solutions, and perhaps doesn't get confused when you attempt to downgrade the other packages.

If nothing else works, you could take the manual approach suggested in this answer: How to Downgrade a Package via apt-get?. Basically, download the necessary .deb packages manually, then install them one by one using the lower-level dpkg and one of its forceful arguments: --ignore-depends, --force-depends, --force-depends-version, or even --force-all.

In the same spirit as the above, you have the --force-downgrade argument:

          downgrade(*): Install a package, even if newer version of
          it is already installed.

          Warning:  At  present  dpkg  does  not  do any dependency
          checking on downgrades and therefore will not warn you if
          the  downgrade  breaks the dependency of some other pack‐
          age. This can  have  serious  side  effects,  downgrading
          essential system components can even make your whole sys‐
          tem unusable. Use with care.

But this assumes that you've read man dpkg, and that you understand what you do:

          Warning: These options are mostly intended to be used  by
          experts  only.  Using  them  without  fully understanding
          their effects may break your whole system.

See Error: version number does not start with digit and How to install an older version of Java and How to install a older version of package like liquid 2.2.2? for examples of:

sudo dpkg --force-downgrade -i your_mesa_package.deb

And see How can I install a package without installing some dependencies? for an example (along with the appropriate warning) of:

sudo dpkg --force-all -i your_mesa_package.deb

Yet another approach would be to create a dummy .deb package using the equivs package (and perhaps a slightly different name). Then installing the dummy package should allow you to remove the "true" package while keeping the relevant deps, and then install the older version. I'm not sure how exactly this would work, but check this relevant thread for details: How to remove a deb without removing its dependencies.