That's exactly what bitcoin achieved with mining. It's the biggest and probably only innovation of a blockchain. Doing it simpler probably isn't possible.
Timestamping is a different problem since there is no need to prevent double spend and less need for extensive data retention other than by the particular people who care about a particular timestamp. You don't need everyone to agree about anything and can cross reference with arbitrarily many external systems for greater reliability. Two of the papers that the bitcoin paper cites are about distributed timestamp systems, and while they aren't exactly what I am looking for they show some basic ideas.