Actually, the complexity of a modern CPU is mainly in making things run fast. Building an in-order, no-cache, single-issue ARM capable of running uClinux doesn't seem all that difficult. The cycle time would be horrible though. You might not live long enough to watch it boot.