gridded ground structure
According to the Texas Instruments "PCB Design Guidelines For Reduced EMI",
"A two-layer board can achieve 95% of the effectiveness of a four-layer board
by emulating what makes a four-layer board better".
The main trick is to use both the top and the bottom layer of your 2 layer board in a gridded ground structure.
I don't think it makes much difference if you route the fast traces on the top or on the bottom.
Either way, you're going to have a horrible slot in the ground plane (on the side opposite those high-speed traces) to get the VCC trace where it needs to go.
In either case, a gridded ground structure helps.
Add a bunch of GND traces parallel to in-between the fast traces that "stitch over" or "staple over" slots in the ground plane on the opposite side.
For example, GND traces between every 2 traces from connector on left to chip on right would look something like:
(top layer)
O---(Vreg)---o----------| (Vcc)
|
O-----------------------| (high-speed data)
o--------------o | (a ground stitch trace)
O-----------------------| (high-speed data)
|
O-----------------------| (high-speed data)
o--------------o | (another ground stitch trace)
O-----------------------| (high-speed data)
|
o----------| (VCC)
and
O o o (VCC)
|
O |
o | o (ground stitch via)
O |
|
O |
o | o (ground stitch via)
O |
|
o
(-- bottom layer, as seen looking through the top layer)
I've seen a rule of thumb that an extra ground trace for every 2 data traces -- increasing the number of traces by 50%, as shown above -- is often adequate.
(An extra ground trace for each data trace -- doubling the number of traces -- would in theory be slightly better).
Usually the "ground stitch trace" is completely invisible on the final board,
because it is completely drowned by a GND copper pour on the same layer.
The only evidence of this design is vias scattered all over the board
connecting GND pours on the top layer to GND pours on the bottom layer.
4-layer prices
p.s.:
You are totally right about the surprisingly high cost of 4-layer boards from most places.
However, have you seen the list of PCB fabs at http://opencircuits.com/PCB_Manufacturers ?
A few have relatively low prices for 4-layer boards if you're willing to wait for 6 weeks (!) --
for example, as of 2013,
OSH Park says "4 layer order: $10 per square inch for three copies of your design. For example, a 2 square inch board would cost $20 [plus shipping] and you’d get three copies of your board."
gridded ground structure references
"A two-layer board can achieve 95% of the effectiveness of a four-layer board
by emulating what makes a four-layer board better". --
Texas Instruments.
"PCB Design Guidelines For Reduced EMI".
"The gridded ground structure works almost as well as
the ground plane, as far as minimizing loop area is concerned." --
p. 7
Tom Williamson.
"Designing Microcontroller Systems for Electrically Noisy Environments".
Intel Application Note AP-125.
1993.
"AVR040: EMC Design Considerations"
http://www.atmel.com/Images/doc1619.pdf
Ross Carlton, Greg Racino, John Suchyta.
"Improving the Transient Immunity Performance of Microcontroller-Based Applications".
2005.