In Solidity, yes, if the first four bytes of an Ethereum's transaction does not contain one of the contract's encoded function calls, then the fallback function will be called.
Since contract code always runs when a contract gets a message, Solidity effectively featurized it into the fallback function.
Note that the Solidity compiler could have "disabled" the feature by generating EVM code that would always do nothing (just uses STOP opcode) or cause an exception if no function signatures match.
Would the transaction get rejected if it has non-zero (i.e. non-0x0)
input data?
At the EVM level, the (input) data field of a transaction by itself has no effect on its validity (for example if a sender has sufficient balance to pay gas for the data, the transaction is valid and nodes should not reject). (Compilers or clients may have their own behavior depending on what they consider desirable or a feature for their users / use cases.)
More details
A very rough example, for conceptual purposes only, of the bytecode that an EVM compiler would produce:
method_id = first 4 bytes of msg.data
if method_id == 0x25d8dcf2 jump to 0x11
if method_id == 0xaabbccdd jump to 0x22
if method_id == 0xffaaccee jump to 0x33
other code <- Solidity fallback function code could be here
0x11:
code for function with method id 0x25d8dcf2
0x22:
code for another function
0x33:
code for another function
With such an example, the Solidity compiler might implement the fallback function code in the "other code" section above. Instead of "other code", to "disable" the fallback function, the Solidity compiler might just have used a STOP or an INVALID opcode.
Since fallback functions can be misused or abused, Vitalik Buterin suggested "establishing as a convention that fallback functions should generally not be used except in very specific cases."