Most people find that consulting is like a ladder; you start at the bottom (or jump up as high as you can to grab a higher step) and as you build up experience, you'll be able to a) get better jobs w/better clients and b) charge more. Putting in time up front is pretty crucial. This isn't to say that you can't try to be uber-ballsy and charge a high rate without testimonials - you just might find it harder.
Personally, I get most of my consulting work through other people that I've worked with before. LinkedIn has been valuable to me, as has Twitter.
You can look to the plethora of freelancing sites; oDesk comes to mind as a well set up for both 'buyers' and 'sellers'.
http://www.odesk.com