Possible to change block type in layout XML?

Changing the block type means changing the block class, so no, but...

... you can just overwrite the block:

1. Find a layout handle which is invoked later OR be sure, that your layout.xml is processed after the block is created, e.g. with <depends> in Company_Module.xml
2. Just create a new block of other type with the same name

The problem is, that this overwrites the block and does not change the type. This means everything which is done on this block between the creation and your change is lost.

For example for changing the catalog.navigation:

<layout version="0.1.0">
    <catalog_category_default translate="label">
        <reference name="left">
            <block type="myModule/navigation" name="catalog.leftnav" after="currency" template="myModule/catalog/navigation/left.phtml"/>
        </reference>
    </catalog_category_default>
</layout>

You can't change it in the layout-files afaik. You can, however, extend and override them in your config-files.

Example:

<config>
    <global>
        <blocks>
            <catalog>
                <rewrite><product_view>My_Custom_Block_Product_View</product_view></rewrite>
            </catalog>
        </blocks>
    </global>
</config>

Remember to extend the original block.