Here's a technique I experimented with recently. My RenderMonkey prototype shows a section of badlands-style canyon, but the same principle should work in caves.
The idea is to start with tiles that are generic, downright boring, with simple predictable edges so they're easy to line up without seams or gaps:
These starting tiles could be shapes you've modelled, or procedurally-generated macaroni tubes of cylintrical geometry (this form is a variant on bcrist's and Steven Stadnicki's suggestions). Using models you've created makes it easier to handle arbitrary topology like branching paths, or points of interest like open caverns. This is still possible with pure procedural (see Gyroninja's suggestion about metaball techniques), but challenging.
Once a tile is placed into the world, displace its vertices using noise functions applied in worldspace. This preserves connectivity and seamlessness between tiles (since coincident vertices have the same worldspace input, and get the same displacement output), but makes every tile look unique and organic:
Texture and normals are applied in worldspace too - here using triplanar mapping - so that adjacent tiles are completely seamless, without tricky UV unwrapping constraints.
The hope is that a technique like this gives you the ease of planning and level design control of a tiled map, without visible repetition or mechanical-looking structure in the playable result.
You can use a lower-res mesh with only the low-frequency noise components applied to create the collision representation. As bcrist notes, you'll need to control the maximum amplitude of the noise relative to the radius and sharpness of turns of the tunnel, to ensure it never pinches off completely.
One further note: if your cave really is infinite, you may need to "recenter" it periodically as the player moves further and further from the origin. Because floating point numbers lose precision at high magnitudes, physics and rendering artifacts can creep in at extreme distances. If you do this, you'll want your worldspace noise to be periodic over a large scale, with the period exactly matched to your recentering offset, so you don't encounter seams after recentering.