Have you tried Nether travelling to widen your search?
Every block you've travelled in the Nether equals 8 blocks travelled in Overworld. All you need is a few supplies (wood, coal, food and some ingots), a compass, a portal to the Nether and enough obsidian to build another portal.
Jump in and walk a long way into one single direction. If you encounter obstacles, mine through them or climb over them. Lava-lakes; build quick one block wide bridges by walking backwards with shift pressed. Just beware of the Ghasts when you build those bridges.
Once you've travelled a good bit, build your portal back to the Overworld, equip your compass and start making your way back to your spawning point and keep an eye out for villages along the way.
I usually have a good rate of success in finding what I need this way, be it villages, certain biomes, etc. etc.
Ok, I created a fresh creative world with the seed and structures on, Have been flying around up to +/- 2000 blocks. Found 3 or 4 desert temples, a desert well, a jungle temple and even a jungle in fire. No villages I could mislooked one though.
For my survival world I did the same trick/cheat and I found only one village. There are too many oceans in my world.
As someome posted above, try nether travelling. 500 blocks in the nether will spawn you 4000 blocks away. You may want to travel even further.
I recommend you to make a creative world for this. And copy down the coords if you find a village.
When I first made my private SMP server, it took us at least a month to find an NPC villager. The first one we found was x=1728,z=1050 which was pretty far away. We had initially only explored a 600-block or so radius from spawn.
They aren't a important as you might think. How much time have you put into the world? If you already have diamond tools and a nice house, just live without a village. If a village is that importand, search for a seed that spawns you in or near a village.
Reading all these frustrations makes me realise how lucky I was with my seed with a village right next to my spawn point. Didn't realise how rare they were. Will post the spawn when I'm back from work if anyone's after a new seed with easy access to testificates. it's nestled on the edge of a hilly and woodland area (not sure what biomes.) Not a bad area to start a world. Having expanded on my village though, I've come to the realisation that they are all robbing low-life's - 5 emerald for a leather helmet! PAH!