すでに解決済みとは思うのですが、今後同じ悩みでここを訪れる方の為にまとめ的に記しておきます。
結果としては、MacかBlutoothキーボードがあれば以下の方法でできます。
Macを使う場合は以下のアプリが1週間無料で使えるので、インストールしておきます。
http://mac.eltima.com/jp/bluetooth-keyboard.html
AppleTV(第3世代)をUSBでiTunesにつないで初期化します。
AppleTVをTV等に接続して起動します。
言語選択画面でキーボード(またはMac)をBlutooth接続します。
Wi-Fiの設定をしないとAppleTVをアクティベートできないので、それだけはやります。
その後自由になるので、何はさておきホームシェアリングの設定をしてしまいます。
それが終われば、Remoteアプリから操作できるようになるので、細かい設定などをすればもと通りです。
私も子供がリモコンを無くしてしまい、iPhoneでリモコン代わりに使っていましたが、AppleTVがおかしくなり、復元しないといけない状態だったので、「リモコンなしで復元方法」を探して復元したら、初期設定ができなくなり、「iOSから設定する方法」で設定したら、「ホームシェアリングの設定はされない」と言う事で、AirPlayは使えるのでコレでいいやと諦めていました。でも、最近MacBookAIRを入手したのでどうにかできないかと試行錯誤して上記の方法で復活させました。
リモコンを買えばいいのですが、ほぼ意地でやりました。