端末によってはroot権限を取得できないようになっており、そのような場合は無理だと思います。
というより、携帯電話でroot権限を取得すること自体危険な行為なので、やめたほうが無難です。

http://nexusonehacks.net/nexus-one-hacks/how-to-install-ubuntu-on-your-android/
を元にすると、簡単な流れは
1. リンク先のzipファイルを展開し、Android端末のSDカードに展開する
2. Android端末のshellでsuを実行してrootになる。
3. 展開したフォルダに入ってsh ./ubuntu.shを実行し、Ubuntuをインストールする。
4. bootubuntuコマンドでUbuntuを起動する。
となります。

あとはUbuntuにデスクトップ環境などをインストールし、Androidからリモートデスクトップクライアントを使ってアクセスします。