here code

<?xml version="1.0"?>
<layout version="0.1.0">
    <catalog_category_default translate="label">
        <reference name="category.products">
        <block type="core/template" name="yourblock" as="yourblock" template="page/myblock.phtml"  output="toHtml" before="product_list" />
        </reference>
    </catalog_category_default>
    <catalog_category_layered>
        <reference name="category.products">
        <block type="core/template" name="yourblock" as="yourblock" template="page/myblock.phtml"  output="toHtml" before="product_list" />
        </reference>
    </catalog_category_layered>

</layout>

here add the code in your layout xml file

    <catalog_category_default translate="label">
        <reference name="category.products">
        <block type="core/template" name="yourblock" as="yourblock" template="page/myblock.phtml"  output="toHtml" before="product_list" />
        </reference>
    </catalog_category_default>
    <catalog_category_layered>
        <reference name="category.products">
        <block type="core/template" name="yourblock" as="yourblock" template="page/myblock.phtml"  output="toHtml" before="product_list" />
        </reference>
    </catalog_category_layered>

And also add the code in

app/design/frontend/yourPackage/yourtemplate/template/catalog/category/view.phtml

add the below code

<?php echo $this->getChildHtml('yourblock') ?>

after end of

   <div class="page-title category-title">
    <?php if($this->IsRssCatalogEnable() && $this->IsTopCategory()): ?>
        <a href="<?php echo $this->getRssLink() ?>" class="link-rss"><?php echo $this->__('Subscribe to RSS Feed') ?></a>
    <?php endif; ?>
    <h1><?php echo $_helper->categoryAttribute($_category, $_category->getName(), 'name') ?></h1>
</div>

Edit: In Xml file type="core/template" is your block type and page/myblock.phtml is your phtml file location