I'd like to create a package which will depend on mysql-server and set the password to its own randomly generated string in case the server is not installed yet. I don't want to have the user put in the password and I'm happy to get the current password from the debconf's file.
But how can I guarantee that my package presets mysql-server-5.1/root_password before the mysql-server package is installed? mysql-server is listed as a dependency of my package.
You cannot guarantee that. In fact, it is guaranteed to work exactly the other direction. From http://www.debian.org/doc/debian-policy/ch-relationships.html:
The meaning of the five dependency fields is as follows:
Depends
This declares an absolute dependency. A package will not be configured unless all of the packages listed in its Depends field have been correctly configured (unless there is a circular dependency as described above).
Your best bet is to make your package work after MySQL is properly installed--possibly by resetting the password, if you really need that functionality.