Except the target of the attack is now out of range. If you had used an immediate reaction to prevent his movement, it would have the same result. As it is impossible to charge into the nearest square towards that enemy, the charge becomes illegal, and the action is discontinued. It is not invalidated, however--you still got to move.
Charges are actually pretty explicit about that... you -must- move to a specific square(or squares), calling out a specific enemy, and move in a specific manner. If you're rendered unable to do these things, charge itself tells you the charge is illegal. Charge is not 'move and attack in the same action' its 'move adjacent to a specific dude, to a specific spot adjacent to that specific dude, and then attack that specific dude.'
I don't think we really want to go down the path of getting into this argument. Suffice it to say that the rules say no such thing. Exactly what bearing that has on the argument at hand though is hard to say. It is quite possible that a charge COULD become impossible to complete, in which case the attack portion of the charge might never take place. That is a bit different situation.
No, because the target is out of range before the attack roll and damage can occur.
Remember, attack resolution happens in a number of steps. A Free Action (or an interrupt for that matter) can be declared at any point along the way. In the case of an interrupt CLEARLY the interrupt can modify at least the step which triggers it even though that step has been executed (IE Shield triggering on a hit and turning it into a miss).
There are really TWO questions with Free Actions. The first is can it interject into another action, and that is clearly answered yes both by the example of Elven Accuracy, AND by the example of warden marking. The second question is whether or not such an interjection can change the result of a step in the resolution of the action it is interjected into. Elven Accuracy again show that this can be the case as it can turn a miss into a hit (or vice versa technically).
Thus the case of pushing an enemy away with a Free Action declared when the attack resolution step 4 is happening would appear to operate identically with Elven Accuracy, changing the conditions of the attack and in this case making it no longer valid (assuming the push puts the attacker out of range of the target). Damage is not dealt until step 5 and we have AMPLE evidence that effects of all sorts can modify the results of attacks even after hit determination.
The example of fighter's CC is not relevant because the 'stops movement' effect is an explicit effect and there would be no basis for it happening at all were the text not there. Of course CC states that a hit causes the enemy to stop moving, that's the whole point of the feature and has nothing to do with its immediacy.
Yes, IMMEDIATE interrupts state clearly that they can invalidate actions. This doesn't in any way tell us that other things cannot do so as well. Interrupts would actually be pretty much pointless if they could NOT do so. This is their reason for existing, so naturally its a significant point that is mentioned.
Now, notice the parallel statement in the Opportunity Action rules block. It never mentions invalidation at all, yet again this is clearly the way the game is played and many other rulings assume this is true. This alone demonstrates that not every section of the rules explicitly spells out every possible consequence of its application.
Beyond that there is a difference between immediate interrupts and immediate reactions which requires careful explication. This is another reason why the immediate actions section goes into the most detail about this topic, because it is making a fairly subtle but important distinction.
Free Actions OTOH don't need to make any such distinctions, they all simply work the same way (there is certainly no evidence that there are differences between them). Given that we have a clear example of one Free Action which clearly behaves in a way identical with interrupts there is simply no other consistent way to interpret the rules except that they all work that way. Given that it creates no (more) rules issues than interrupts do already and avoids a whole class of ugly problems one must ask why it would be desirable to treat Free Actions in an inconsistent manner.
It would actually be interesting to see what one of the devs would have to say about this conversation. Unfortunately the quote of Trevor didn't really address it as he seems to be assuming a context where the enemy is moving. Even an Immediate Interrupt push would work the same way in that case, so we actually learned nothing that bears on the use of a Free Action during an attack.