Rarely will you get a broad enough mandate to actually pull it off (based on your description). The other problem is entirely custom solutions put companies off because they then have to rely on your for support (one lucrative area that I do consultancy is supporting such programs for companies silly enough to go that route :) costs 'em a fortune). A custom solution sounds expensive from a companies perspective; both in cost but also in development time.
But most importantly the concept of "data liberation" and custom built databases are just not really on the commercial radar at the moment. Selling it to them could be pretty time consuming. To give you an example Im currently working with a company that are doing some pretty cool things - they've asked me to work on expanding their web app and database. It's a total mess and I have suggested a complete redesign which will cost about the same and be a lot easier for the both of us; they are resisting like hell...
(this is purely my opinion ofc, YMMV)
Not to put you off; but it is worth considering it from this perspective now rather than later. To answer your questions:
Where should I look for my first client?
People you know. I started contracting through a friend who, via religious connections, had a lot of eager clients/friends with work. However based on your description this is probably a very hard market to sell to.
Would I have to link up with an existing consulting firm or can individuals find success in this space?
Depends how much success you want - but I would say no. The resources and tools (legal templates, time tracking, invoicing) are now freely available on the web with a little looking. The only real need you may have is getting a foot in the door with large corps (which strike me as your target market).
Is this even a problem that businesses acknowledge?
See above. I suspect you will have to work pretty hard to sell this as a concept - at least initially.