Is your new radiator a modern one with full-size threads at the top? (Like these)
View attachment 294303
And is your boiler pressurised? (No tanks in the loft, filling loop by the boiler)
If yes then I've had success by;
Acquire a spare radiator tail, a length of garden hosepipe, some PTFE tape and a big bucket.
If it's a short length of hosepipe (3' or so) fit it over the rad tail (hot water helps), fix it on with a jubilee clip or a cable tie if you have them to hand.
Switch heating off
Close both valves on the rad you're going to bleed (we'll start with the new one)
Bleed that rad (with the bleed valve) til water stops coming out.
Remove one of the chrome plugs at the top of the rad, replace it with your spare valve tail.
Attach the end of the hose to the valve tail (if you haven't already done that), stick the other end in the bucket (preferred- easier to see/hear air bubbles) or in a drain.
Ideally you'll have a friend here at the boiler.
Get your friend to turn the filling loop on and off to maintain about 2 bar pressure (avoid going above 3).
Turn one of the radiator valves on to full. Listen/watch for air pockets coming down the pipe, run it for at least a minute (if using buckets, try and have 2 so you can keep the flow going).
After a minute, close the open rad valve then open the other rad valve.
Again run for at least a minute.
Close that rad valve.
Tell your friend to close the filling loop.
Wait til water stops coming out of the hosepipe.
Remove the rad tail.
Refit the chrome plug.
Bleed system/operate filling loop til pressure is at 1 bar or so.
Try the heating.
If that doesn't shift the airlock you will have to repeat the trick on an upstairs rad (but from the sound of it upstairs is decorated and you'll always get some spillage doing this trick).