つかれた...

IMEIの代わりになるようなものを調べてみたところ、

UUIDは、分散システム上でどこかが統制を取らずとも、一意に特定可能な識別子の作成を目的としており、UUIDは重複や偶然の一致が起こりえないと確信して用いることができる。

UUID - Wikipedia

とあり、UUIDが使えるんじゃないかなぁと思った。*1

UUIDをAndroidで生成する方法を調べてみたところ、UUID.randomUUID()が使えそうかと思った。
が、よく見てみると、

Generates a variant 2, version 4 (randomly generated number) UUID as per RFC 4122.

UUID  |  Android Developers

とあった。version 4ってなんやねんってことでぐぐったら、

Version 4 UUIDs use a scheme relying only on random numbers. This algorithm sets the version number as well as two reserved bits. All other bits are set using a random or pseudorandom data source.

Universally unique identifier - Wikipedia

とある。Version 1はMAC addressを用いるとあるがVersion 4は...どうなんだろね?
Android2.3.7でざっと見た感じ、単に/dev/urandomとかを使ってるように見える。
まぁ正直かぶることはまずないと個人的には思うんだが...UUID.randomUUID()つかっちゃ駄目なような気がする。
100%かぶらないとは言えないと思うので...あーでもどうなんだろ?
とりあえずサーバ側でユニークなIDを生成して渡すようにするってのが無難な気がする。
なんかのセキュリティの本に乱数の話がちょろっと書いてあって、/dev/urandomでもだいじょうぶかもなんてあったような気がする...がこの場合はどうなんだろ...

とりあえず2.3.7の眺めたソース...

UUID#randomUUID()

 public static UUID randomUUID() {
     byte[] data;
     // lock on the class to protect lazy init
     synchronized (UUID.class) {
         if (rng == null) {
             rng = new SecureRandom();
         }
     }
     rng.nextBytes(data = new byte[16]);

SecureRandom()

public SecureRandom() {
    super(0);
    Services.refresh();
    Provider.Service service = Services.getSecureRandomService();
    if (service == null) {
        this.provider = null;
        this.secureRandomSpi = new SHA1PRNG_SecureRandomImpl();

SecureRandom#nextBytes(byte[] bytes)

public synchronized void nextBytes(byte[] bytes) {
    secureRandomSpi.engineNextBytes(bytes);
}

SHA1PRNG_SecureRandomImpl#engineGenerateSeed(int numBytes)

protected byte[] engineGenerateSeed(int numBytes) {

    byte[] myBytes; // byte[] for bytes returned by "nextBytes()"

    if (numBytes < 0) {
        throw new NegativeArraySizeException(Integer.toString(numBytes));
    }
    if (numBytes == 0) {
        return new byte[0];
    }

    if (myRandom == null) {
        myRandom = new SHA1PRNG_SecureRandomImpl();
        myRandom.engineSetSeed(RandomBitsSupplier
                .getRandomBits(DIGEST_LENGTH));

RandomBitsSupplier

static {
    AccessController.doPrivileged(
        new java.security.PrivilegedAction() {
            public Object run() {

                for ( int i = 0 ; i < DEVICE_NAMES.length ; i++ ) {
                    File file = new File(DEVICE_NAMES[i]);

                    try {
                        if ( file.canRead() ) {
                            // BEGIN android-modified
                            bis = new FileInputStream(file);
                            // END android-modified
                            randomFile = file;
                            serviceAvailable = true;
                            return null;
                        }

SHA1_Data#DEVICE_NAMES

// BEGIN android-changed: /dev/random seems to be empty on Android
static final String DEVICE_NAMES[] = { "/dev/urandom" /*, "/dev/random" */ };
// END android-changed

*1:ていうか...ぐぐったらUUIDなサンプルがみつかったので