You are totally possible to edit toolbar as you want, only need to go to this file ..\app\design\frontend\base\default\template\catalog\product\list\toolbar.phtml
I have just had a small change in this file, and I see that it is look similar to your illustration images. I also attach you the file that I edited. It is very simple for you to take it. I think that you need to continue editing it to fit your requirement. Hope you succeed.