In other words, that there exists a nonce for the block that will result in sha256(sha256(block header + nonce)) hash under the current difficulty barrier number.
The clients make use of the Target to determine if a block hash is valid and will be accepted by the network. The Bitcoin wiki states the following:
The target is a 256-bit number (extremely large) that all Bitcoin clients share. The SHA-256 hash of a block's header must be lower than or equal to the current target for the block to be accepted by the network. The lower the target, the more difficult it is to generate a block. [...]
Each hash basically gives you a random number between 0 and the maximum value of a 256-bit number (which is huge). If your hash is below the target, then you win. If not, you increment the nonce (completely changing the hash) and try again.
The current target value can be found here: http://blockexplorer.com/q/hextarget
No, there is no way of proving that a hash exists other than actually finding that hash. (i.e. brute force). The existence of a method of being able to predict the result of a hash other than computing the hash would render the hash function cryptographically unsound. (And so we can infer that no mathematician has found such a method for SHA-256).
That said, as discussed in this other Q&A, there are a number of characteristics of a block that are dynamic so it isn't as if an "insolvable" block would actually cause any network problems.