Hi Nomi,
I just finished a site (using 1.6.8) that pulls random testimonials on each of the pages. I would think the logic could be similar. I ended up creating a weblog (or, a channel as their called in 2.0) for the client to add their testimonials as entries. Then on the main page template, I used an embed. The embedded template is just a simple channel pull, that is limited to 1 and set to pick a random entry. Works great for my site.
I’ve read that embedded templates could possibly cause a performance hit. I made certain to disable everything feasible with the “disable” tag. With or without the embed, I have noticed no performance difference.
I might also suggest the Query module with a direct SQL statement to pull this channel information into your template as well; though I have yet to try it, in theory, I think it should work.
If you were looking to tie these testimonials to other entries, you could establish relationships by creating a new fieldtype that populates with your testimonials.