[pjc50]

You can get built in decoupling capacitors: https://www.mill-max.com/products/socket/122-XX-XXX-41-80100...

You could certainly estimate the clock frequency in advance. The things that are going to cause trouble are transmission line effects (ie pulse length no longer >> wire length), and the usual digital logic critical path constraints: wire and gate delays; clock skew and drive strength; fanout constraints.

More decoupling doesn't help you once you have enough to prevent crosstalk through the power supply. Star-routing the power and ground may be a good idea.

I've done 20MHz. Coincidentally this is the limit of cheap scopes. This page claims 33MHz is achievable, and gives a good explanation of why: http://www.sigcon.com/Pubs/news/2_8.htm

Some good tips: https://www.pjrc.com/tech/8051/dev-board-wirewrap.html

Reccomendation to use the kind of board with built-in ground plane (sounds good if you can find it): http://www.williamson-labs.com/prototype-lt.htm

For IC availability, check your local Digikey. Note that 68k is still being manufactured as "Coldfire" by Freescale (with slight backwards incompatibility).