What is the problem that mining solves? Of course, the function of mining is to secure the blockchain, but I'm looking for a more abstract summary of what the exact problem is that mining tries to solve? I believe its called the Byzantine Generals problem, but can it be described in a couple of sentences?

The network needs to select one random stranger out of a large group at a fixed schedule, and uses a 'hashing-lottery' as a reasonably fair method to do so. Is that a good definition of the reason why POW is needed?

In other words: Suppose I developed an alternative method to select a random p2p node every few minutes, who gets to publish the next block, could that replace cpu-based proof of work?
In my opinion, it is one of the greatest misconceptions about Bitcoin that miners solve a "hard problem". Many news sources explain it like that, but in fact it's not true.

All a miner does is guessing until he got something right. A miners takes his block of transactions (including the coinbase transaction that sends the fees and block reward to himself) and calculates the hash of it. Hash calculation is a very common procedure and is not at all "hard". The hash he gets needs to match a certain condition. This condition gets harder as more miners try it (see Difficulty). When the miner got a hash that fits the condition, he can publish it to all other Bitcoin clients and the block is added to the block chain.

The reason that miners with more computer power have a larger chance of winning the block is because they can simply guess faster. They can calculate more hashes per second to test against the condition, (Mining power is expressed in Hashes/second.)

The need for proof-of-work is there because the Bitcoin protocol wants that a block is found only once every 10 minutes approximately. So, as more miners enter the game, it has to become harder to do. The POW makes sure that finding a block is not easy and takes the some time. That's also the reason that the difficulty raises as more people mine. Every 2 weeks, the algorithms adjusts the difficulty so that again one block is found every 10 minutes at the average hashpower of the previous two weeks.

So, to answer your second question: If you could find an alternative method for achieving exactly the same thing as currently is done in Bitcoin mining, it could replace it. But Bitcoin is programmed as it is and won't probably ever change this method. But there are alt-coins that use different methods for distributing the coins and securing the block chain.