> 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.

That being said, if you want to be 100% sure, 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](http://wiki.cyanogenmod.org/w/Devices/en#vendor=;) 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 for the average user would be to port/compile [CyanogenMod](https://wiki.cyanogenmod.org/w/Doc:_porting_intro) or [AOSP][1] from source. 


  [1]: https://source.android.com/source/requirements.html