Di gratuito c'è ilbello.com, l'avevo provato circa un anno fa ma era davvero un chiodo, quasi inutilizzabile pure per i test, forse adesso l'hanno migliorato un po'...

Altrimenti adesso ci sono diversi hosting economici compatibili con Magento come ad es. spaziorc.com e register.it.

In ogni caso per un'installazione di Magento in produzione conviene sempre lavorare su un server ottimizzato per lo scopo e non su un hosting di basso livello.