For the case dpkg doesn't work also, you can use the old way:

Download the mysql libs here: http://dbg.killtube.org/libcod/libs/mysql/

Start like this:

Code:
LD_LIBRARY_PATH=/folder/to/libs/mysql LD_PRELOAD=libcod2_1_3.so ./cod2_lnxded +set fs_game ...
or:
Code:
export LD_LIBRARY_PATH="/folder/to/libs/mysql"
export LD_PRELOAD="libcod2_1_3.so"
./cod2_lnxded +set fs_game ...
For the case that's not working also, I've compiled libcod without the mysql-dependency: http://killtube.org/downloads/libcod/

Edit: Silent requested some files, old files are down: http://killtube.org/downloads/silent/