I'm also on Android in Europe, with no YouTube Music subscription, and it lets me play music in the background, without ads, if it's either on the device or in the "Uploads" section (which is where it's put music I'd purchased on Google Play Music). So it looks like they haven't completely removed that functionality, although the interface for accessing it is significantly more annoying.