Electronic – Noise everywhere on solderless breadboard, could the DC-DC converter be the source

There is of course no single answer to what "decent" power supply noise is. That's like asking what a decent car is without telling us whether its for driving around a racetrack or back country dirt roads.

Whether the values you mention are decent depends on how that power rail will be used. What you really seem to be asking is just from the power supply's point of view whether these value seem reasonable or not. 20mV for a generic bench top supply sounds quite reasonable to me, and so does 7mV for a on-board boost converter (in fact that's actually quite good compared to a lot of them).

Your circuit, however, may have a different opinion. If the 5V supply is just powering digital circuitry, then it's a lot cleaner than it needs to be. Even 100mVpp ripple would be tolerable.

If you're powering sensitive analog circuitry, then 7mV could be large. In that case the frequency content of the ripple also matters. Most analog ICs have a power supply rejection spec. There is active electronics in the IC to make its operation somewhat independent of the power supply voltage. However, that electronics can only react to noise up to some frequency. The frequency requirements to get the specified power supply rejection ratio is rarely specified. It's a good practice to put a ferrite bead or small chip inductor followed by a ceramic cap to ground on the power leads of analog parts. This will attenuate the high frequencies of the noise, with the remaining low frequencies hopefully in the range the part can handle and reject actively.

Some parts are much more susceptible to this than others. The first time I used one of the Freescale multi-axis accellerometers there was a lot of noise on the output. The power supply noise actually seemed to be amplified onto the output. Adding the aforementioned chip inductor in series with cap to ground on the power lead helped a lot to clean up the output signal.

To answer your last question, the normal way to look at power supply noise is exactly what you did. AC couple the scope input, crank up the gain, and look at the size of the resulting mess.

You'll need a switcher to pump up the input voltage, and have it followed by a linear regulator, like Russell proposes. His TPS717xx, however, while having a high PSRR doesn't have a high output current (150mA). High current and high PSRR don't go together well on LDOs. Nevertheless, an LDO may be required, since the 2-4V input volatge suggests that you're powering from batteries, and then you don't want to lose too much power in regulators.
A solution for the PSRR may be to use 2 LDOs in cascade, so that the PSRRs add.
The LP3878-ADJ may be a good choice for your second stage; it's low-noise, can supply 800mA and has an adjustable output which can be set to 5V.
For the preceding stage you could use an LP38690-ADJ. The datasheet shows how you can improve ripple rejection at higher frequencies if you place a 100\$\mu\$F output cap. Caps between each stage (100\$\mu\$F + 10\$\mu\$F + 1\$\mu\$F) are a must, but \$\pi\$-filters are a better idea: caps + ferrite bead + caps. Those should suppress the higher frequencies generated by the switcher.

edit (re your update)
Dave rightly has second thoughts on your using AA batteries, but it's even worse than he calculated. I estimate that you'll need 7V from the switcher to feed the cascaded LDOs, so 600mA @ 7V is 4.2W, at a conversion efficiency of 80% that's 5.25W from the batteries. Two AA cells deliver 3V, so that's 1.75A from the batteries! Not only won't they last long, they won't like it either. I suggest you use a LiPo cell, which delivers 3.7V with a boost regulator, or even two cells in series, giving 7.4V, and use just the LP3878-ADJ. (If you don't use a switcher you don't need the second LDO to suppress its ripple.)