Fermo restando che i CSS sono talmente utili e comodi che farne a meno è quasi un delitto, ecco due esempi di come puoi cambiare gli stili senza dover utilizzare classi CSS:

Esempio1
codice:
mio link
Oppure (senza tirare in ballo in maniera più seria gli eventHandler):
codice:
<script language="javascript" type="text/javascript">
<!--
function cambiaStile(mioLink, e) {
    if (e == 'over') {
        mioLink.style.color = #654321';
        mioLink.style.textDecoration= 'none';

        // Aggiungi tutti gli stili che vuoi...

    } else if (e == 'out') {
        mioLink.style.color='#000066';
        mioLink.style.textDecoration= 'underline';

        // Aggiungi tutti gli stili che vuoi...

    }
}
//-->
</script>

mio link
questo però implica l'uso di javascript.
Come ti hanno suggerito in precedenza, non hai alternative...