[General Questions and Answers] f0k:
Finally got around continuing this quest, and it worked! I deodexed the BackupRestoreConfirmation.apk, resigned it, installed it as a system app, and can now run adb backup on my Xperia Ray, Android 4.0.4 ICS.

For posterity, I am documenting all required steps (assuming a Linux machine).

1. Download and extract a stock system image

Download a system image for Android 4.0.4: https://dl.google.com/android/repository/sys-img/android/sysimg_armv7a-14_r02.zip

Unzip it.

Extract the image with unyaffs (can be installed with apt install unyaffs in Ubuntu):

mkdir /tmp/sysimg
unyaffs armeabi-v7a/system.img /tmp/sysimg

It will say Warning: Can't restore owner/group attribute, run unyaffs as root, that can be safely ignored, we do not need files to be owned by root.

2. Deodex BackupRestoreConfirmation.apk

Download smali and baksmali (https://github.com/JesusFreke/smali, find download link in the README), put the two .jar files somewhere (I assume /tmp)

Extract the .odex file. java -jar /tmp/baksmali*.jar x --help is pretty self-explanatory. I did:

mkdir /tmp/backuprestore
java -jar /tmp/baksmali*.jar x -a 14 -d /tmp/sysimg/framework -o /tmp/backuprestore/out /tmp/sysimg/app/BackupRestoreConfirmation.odex

Assemble the smali files into a .dex file. Again, java -jar /tmp/smali*.jar a --help is pretty self-explanatory. I did:

java -jar /tmp/smali*.jar a -a 14 -o /tmp/backuprestore/classes.dex /tmp/backuprestore/out

Add the .dex file to the .apk file. We will copy the .apk to be sure.

cp /tmp/sysimg/app/BackupRestoreConfirmation.apk /tmp/backuprestore
cd /tmp/backuprestore
zip BackupRestoreConfirmation.apk classes.dex

It is not needed to do a new zipalign. If you're curious, you can install it (in Ubuntu, sudo apt install zipalign) and run zipalign -c 4 BackupRestoreConfirmation.apk && echo aligned || echo not aligned to check it.

If you try to install the file with adb install BackupRestoreConfirmation.apk now, it will say: Failure [INSTALL_PARSE_FAILED_NO_CERTIFICATES], because it is not correctly signed any longer. We need to resign it.

Install signapk (in Ubuntu, sudo apt install signapk. If you want, you can first verify that it is indeed not signed:

jarsigner -verify BackupRestoreConfirmation.apk

It should say jarsigner: java.lang.SecurityException: SHA1 digest error for classes.dex.

The original .apk is signed correctly; with

jarsigner -verify -verbose -certs /tmp/sysimg/app/BackupRestoreConfirmation.apk

you will see that it was signed by "EMAILADDRESS=android@android.com, CN=Android, OU=Android, O=Android, L=Mountain View, ST=California, C=US" with a 2048-bit key.

Create a key for signing. This can be done with keytool, but this will set up a keystore that will be left behind. Instead, I followed a guide from https://sites.google.com/site/delocatedsystems/android/howto/create-cert-signapk, using 2048 instead of 1024 bits:

openssl genrsa -out key.pem 2048
openssl req -new -key key.pem -out request.pem # this will ask for some data, make up something
openssl x509 -req -days 9999 -in request.pem -signkey key.pem -out certificate.pem
openssl pkcs8 -topk8 -outform DER -in key.pem -inform PEM -out key.pk8 -nocrypt

Finally, we can sign the .apk:

signapk certificate.pem key.pk8 BackupRestoreConfirmation.apk BackupRestoreConfirmation_signed.apk
mv BackupRestoreConfirmation{,_unsigned}.apk
mv BackupRestoreConfirmation{_signed,}.apk

And optionally verify it with jarsigner -verify BackupRestoreConfirmation.apk -certs -verbose.

3. Install BackupRestoreConfirmation.apk

If you just install it with adb install BackupRestoreConfirmation.apk, it will be installed as user app. If you then run adb backup, the confirmation dialog will appear as intended. But if you confirm it, you will get:

D/BackupManagerService( 292): acknowledgeFullBackupOrRestore : token=1892071259 allow=true
D/AndroidRuntime( 8310): Shutting down VM
W/dalvikvm( 8310): threadid=1: thread exiting with uncaught exception (group=0x2b542210)
E/AndroidRuntime( 8310): FATAL EXCEPTION: main
E/AndroidRuntime( 8310): java.lang.SecurityException: acknowledgeFullBackupOrRestore: User 10104 does not have android.permission.BACKUP.

(Uninstall again with adb shell pm uninstall com.android.backupconfirm if needed.) So the .apk must be installed as a system app to have the android.permission.BACKUP permission.

To do so, copy the .apk file to your device:

adb push BackupRestoreConfirmation.apk /data/local/tmp

Now open a root shell on the device. This can be done via an exploit I explained in another post. Assuming you are in a root shell on the device, do:

remount -o rw,remount /system
cat /data/local/tmp/BackupRestoreConfirmation.apk > /system/app/BackupRestoreConfirmation.apk
chmod 644 /system/app/BackupRestoreConfirmation.apk
remount -o ro,remount /system
exit

In my case, the app was picked up directly, without having to reboot the phone. Verify with:

adb shell pm list packages -f | grep -F backup

If it worked, the list will contain:

package:/system/app/BackupRestoreConfirmation.apk=com.android.backupconfirm

Otherwise you may need to reboot your phone with adb reboot.

When you now try to backup an app with adb backup -f theappname.ab -apk com.theappname (where com.theappname is taken from the list of user apps produced with adb shell pm list packages -3), you may find that instead of a 0-byte file that you get with a missing BackupRestoreConfirmation.apk, you get a 41-byte file, which is only a moderate improvement. In adb logcat, you may find:

V/BackupManagerService( 811): Requesting full backup: apks=false shared=false all=false pkgs=[Ljava.lang.String;@4181ffc8
W/BackupManagerService( 811): Unknown package '-apk' 'com.theappname', skipping

It may not be apparent at first, but the quotes around -apk and com.theappname in the error message are not put there by BackupManagerService, they are introduced by recent versions of adb to safeguard against a shell injection. This is why -apk is not detected as a flag, and the package name is not recognized as a package. The solution is to downgrade to an earlier version of adb, as explained in more detail on https://android.stackexchange.com/a/132921.

To check the version of adb on your computer, run:

adb version

To check the version of adb on the phone, run:

adb shell adb version

In my case, the phone is running 1.0.29, but downgrading adb to 1.0.31 was enough. Precompiled versions are available for Linux, Mac, Windows.

Finally, you can backup apps with adb backup (at least those apps which support it). Phew!

(PS: If you want to run adb backup -shared, you will need to deodex and install SharedStorageBackup.apk. Didn't try.)