Cicindelaで遊ぼうと思ったところ普通のレンタルサーバでは難しいようだったので、さくらVPSを借りることにしました(現時点でまだ試用期間中ですが)。
仮想サーバですがroot権限ももらえて好き勝手できるすごいやつです。月額980円。

自由度が高い半面、セキュリティなども自分で考えないといけないので初心者には大変です。とりあえずやったことをメモ。

まず下記を参考にして初期設定。
http://blog.myfinder.jp/2010/09/vpsssh.html

あとはここを参考にしてApache、PHP、MySQLをさくさくインストール。
http://blog.mobf.net/archives/151

バーチャルドメインの設定も。
http://blog.mobf.net/archives/157

nackle.comはcoreserverで運用していますが、一部のサブドメインだけさくらVPSで運用することにします。つまり特定のサブドメインのみさくらVPSのIPを指すようにすればOKなので、僕の場合は既存のDNS設定に「a hoge xxx.xxx.xxx.xxx」だけ追加すればOK。

SSHのポートも変更。デフォルト(22番)のままだと危険らしい。
http://akabeko.sakura.ne.jp/blog/2010/09/さくらのvps-を使いはじめる-2/

さらにiptablesを設定して、開放するポートを限定。
http://akabeko.sakura.ne.jp/blog/2010/09/さくらのvps-を使いはじめる-3/

とりあえず今のところそんな感じ。