How do you actually setup a vesting agreement for co-founders w/out breaking the budget?

Before getting into some of the details, I'll give you the bad news first: You can't do this (properly) by yourself. It would be difficult for any entrepreneur, but based on your confusion of terms ("share' and "shareholder" refer to corporations rather than LLCs), it is evident that you are new to these issues.

In the following discussion I will assume that a corporation is involved. (If you want to do something similar with an LLC, the appropriate terms - in the U.S., at least - typically are "member" and "percentage membership interest" or "units", depending on how the LLC's operating agreement is written.)

Each founder typically signs a restricted stock agreement under which he is granted - and immediately owns - shares. Over time, the portion of shares that is subject to forfeiture is reduced - e.g., 25% per year for four years. Because this amount is a decreasing percentage, rather than the increasing percentage associated with stock options, the process often is referred to as "reverse vesting" (in contract to option "vesting"). For additional information, please see "Rewarding Key Personnel: Restricted Stock or Options?"

Part of your confusion arises from not knowing the difference between authorized shares and issued shares. Please see "How Many Shares Should My Corporation Authorize and Issue?"

Disclaimer: This information does not constitute legal advice and does not establish an attorney-client relationship.

1. If you don't have an LLC yet, check out http://foundrs.com, it will do what you want for essentially nothing. It's not a company structure, it's a share vesting agreement among co-founders.
2. If you have an LLC: the way it works (at least in the US) is that the founders own all their shares up-front, but if they leave, they promise to return the unvested shares. This is slightly different from stock-options, where the employee doesn't actually own shares until the options are exercised. As you noticed, you can't obviously have options only, there has to be shares around. That's why usually first founders get shares with vesting through buy-back, and everyone else (employees) get stock-options. But I recommend checking your local lawyer, because stock is heavily regulated and you are sure to mess up completely if you don't get professional advice.

Check out this post by Brad Feld. I actually read it earlier today. If it's an informal company you can probably write or template the vesting agreement yourselves.

In regards to the second question, if you have four founders who each own 25% of the company but are vested at 0%, and one of them leaves, now each employee owns 33% of the company (still vested at 0).

Just because you haven't vested it yet doesn't mean you don't own it, you just haven't earned it yet.

If you go through a full blown VC agreement I believe you can structure this more specifically (i.e. if a founder leaves, the other founder gets their forfitted shares instead of it going equally among the owners (i.e. "reverse dilution").