It's lovely. Very expressive. It's like a sort of meditation on the tune. No - you couldn't dance to it !
I'm not sure why printed versions might render it in 2/4. 4/4 or 'cut common' seem more appropriate to me. (When I refer to bar-numbers below I'm thinking in 4 to a bar.)
In those first bars he is just reminding himself of the tune; feeling his way into it. I think this is an ancient practice, similar to (though certainly not influenced by) the alap of North Indian classical music: 'unmetered, improvised and unaccompanied'. In Europe no doubt similar mental processes led to the development of the toccata: the need of the lutenist to check his tuning and try and remember the tune someone's requested! It's certainly unmetered, and those bars are sort of unaccompanied: it's two-part writing really, with no chords in the right hand and only broken chords in the left.
Yes - those first few bars would be hard to notate in in any time signature. In Sibelius you would need to use considerable jiggery-pokery. It would be easier to notate them by hand because you could indicate how rapidly the notes were to be played graphically by putting as many of them as you liked into each bar and bunching them up closely or less closely. This is called space time notation, normal note values being replaced by the horizontal spacing of note heads on the staff. (Cage and Lutosławski do this sometimes. Sibelius doesn't!)
You're right about rubato. There are two types: your jazz type, where the stolen time gets repaid, and the type where everyone slows down or speeds up together and there is no catching up. Malena is the second type.
But no, there's no logic to his use of rubato. We could say he's interested in the expressive potential of the piece and that where the notes of the melody are poignant, or where the harmony is richer (the Fm6 for example), he finds more scope for invention. Where he can't see much potential he moves on quickly. In bar 8 [ignoring the intro bar] where a - somewhat ordinary - Cm is expected, he adds a b9 to the C7 and brings it forward to the beginning of the bar, keeping up the emotional energy. Repose is only allowed where it will provide contrast. And he's interested in the contrast between the major-key stuff (which is like a flashback to happier times) and the minor key of the main tune.
Those seem to be the 'rules'. There are really only suggestions of tango, aren't there? Rather fleeting ones. You've probably noticed there are bars of 3/4 in there occasionally. They're not rubato: they're 3/4!
If I were writing it out in order to learn it I wouldn't worry too much what it looked like, and it'd be full of instructions like 'Move on' and 'Hold back', á la Copland. And I'd include a reminder to use hardly any pedal: his use of it is amazingly subtle, isn't it?
Good luck. And thanks - I'm glad to have got to know that piece.