You are correct that there should be some space between the lever and handlebar when the brakes are fully applied.
I think I can assume that you have set up the calipers so that the pads are the correct distance from the wheel rim - a few millimeters (or a bit more if your wheels are a little out of true), as you say that adjusting the cable causes the pads to rub on the rim.
If the lever hits the handlebar there must be excess slack in the cable somewhere.
You say that adjusting the cable at the caliper or using the barrel adjuster does not improve the lever travel. If you pull the lever, does the caliper move immediately, or if there cable slack being taken up before the caliper moves?
I'm guessing that something is binding in the cable run somewhere causing the caliper arms to retract to a certain point, but there is still slack cable between the caliper and lever.
You can check the cable run between the lever and caliper, ensure the housing is properly seated, unhook the caliper and check the cable runs smoothly in the housing. Apply tension to the cable by gripping it with some pliers and check the lever pulls it immediately.
You could also choose to replace the cable and housing, which is a common thing to do when tuning up a bike.
You can check if you have set the brakes up properly be checking out some online resources. Park Tool Company has some great brake adjustment videos on their YouTube channel. Here is the V-brake video.
Update based on new info in comments:
The problem seems to be: one caliper arm is retracting less that the other and then rubs on the rim. You then find you need to slacken off the cable to stop that non-retracted arm from rubbing.
The solution is, of course, to fix the non retracting caliper arm. It's a common problem for the V-brake arms to get sticky and not retract symmetrically.
Remove the caliper arms, clean the arm bushings, posts and springs, re-grease and reassemble.
Adjust the spring tension screws on the caliper arms so that the arms retract symmetrically (see picture below).
