I have linux (Ubuntu) server which I have root access to through ssh (port 22) only. On that server there is a MySQL database listening on port 3306. Is it possible to use putty (on my machine) and tunneling (on the linux machine) to create a tunnel from a local port on my machine (say 4000), to the linux server on port 22 and then from the server to itself on port 3306 ?
The simple answer is yes, but please note that the tunnel is actually started on your computer. The way it works is that you create an SSH connection to the server (which is secure) and then instruct the SSH to listen to a port on your side and forward whatever connections come in - to a specific port on a specific host address on the server side. The target of the tunnel need not be the same server - it can be any other valid address, which - in the case its not the server running the SSH server itself - will see the incoming connection as if it came from the SSH server instead of from your client.
To set it up, open the Putty configuration dialog, select the setting of the connection you normally use to access your server and click "load" (and not "open"). Then in the tree on the left side, navigate to Connection->SSH->Tunnels and create a new "local" tunnel with the source port 4000 and the destination "localhost:3306" (because the destination address is resolved on the server, from the server's point of view the MySQL port is on the localhost). Then navigate back to "session" and click "Save" to keep your settings for the next time. Now you can use the saved connection to log in to your server and after you successfully log in, everytime you connect to port 4000 on your computer you will actually connect to port 3306 on the server.
If you are seriously into tunnels, and running an MS-Windows client, then I suggest looking at Putty Tunnel Manager which uses Putty to set up and run tunnels easily without needing to have an open putty console.