Will I be able to detect such malware (Android.Trojan.Uupay.D and the
likes) using any (free) android antivirus ?
No, if it was detectable by a free or even paid antivirus, the company wont ship the device with the malware, as it will bring down sales drastically. They have a reputation to maintain!
Is it really impossible to remove them (GData says so) ?
No.
If you want to be 100% sure that the device is clean, then you must remove the OS that came with it and flash a trusted(opensource) ROM like official CyanogenMod. So before buying the phone, check if you can get one. Here is a list of devices that support CyanogenMod.
If a official cyanogen or other ROMs are not available and you still want to buy the same device, an impractical advice to the average user would be to port/compile CyanogenMod or AOSP from source.