I need ideas for a complicated menu

I have a slightly complicated menu to code from PSD document and integrate into wordpress.

this is how it looks:

(link in the comment bellow)

The result of my work is this: http://slavisaperisic.com/FlexE/meni_setap.html

Now, when I write function I get the default markup

<ul>
<li class="page_item"><a href=""></a></li>
<li class="page_item"><a href=""></a></li>
<li class="page_item"><a href=""></a></li>
</ul>

But the markup I created (that gives me the appropriately styled dynamic menu) looks like this:

<div id="menu">

                    <div id="menu-left"></div>
                    <div id="main-menu">
                        <ul>
                            <li class="active first">
                                <div class="left_li"></div>
                                <a href="#" class="active">Exploring</a>
                                <div class="right_li"></div>
                            </li>
                            <li class="second">
                                <div class="left_li"></div>
                                <a href="#">Using</a>
                                <div class="right_li"></div>
                            </li>
                            <li class="third">
                                <div class="left_li"></div>
                                <a href="#">Downloading</a>
                                <div class="right_li"></div>
                            </li>
                        </ul>
                    </div>
                    <div id="menu-right"></div>

                </div>

I styled it so that it follows the length of the word in the menu item. Obviously I can’t use the wp_list_pages() function because the structure it gives me is different than the one I need.

Do you have some ideas? Maybe point me to somewhere where I can learn to code it differently or explain it to me?

Thanks