The area between Panama and Colombia is the Darien Gap. There is not road between them as it is a very dense and humid jungle, but it can be crossed by boat. Be aware that it is a potentially unstable area where guerrilla and paramilitary groups can be active so you need to check locally before travelling there. No incidents with tourists have been reported there though and these people seem to be far from the coast in the jungle.
You have to fly from Panama to Puerto Obaldia (www.aeroperlas.com - aprox 80 USD w/taxes). From there you get you Panama exit stamp and take a boat to Capurgana in Colombia, where you get you entry stamp to Colombia. It is a very nice, quiet and safe beach town where you can stay for a while. Then you have to take another boat to Turbo where you can catch a bus to Medellin. Make sure you do this bus ride during the day.
The following post provides detailed information on how to do it:
http://www.lonelyplanet.com/thorntree/thread.jspa?threadID=1288537&tstart=1380
I think it would be cheaper to fly back from Colombia to Mexico City, since there are 2 airlines doing direct daily flights, and 2 other connecting in Panama and San Jose. I am not totally sure though. www.despegar.com is a good website to check for flights in South America. I am guessing though that since you are going to Colombia before Venezuela. Then it would probably be more practical to fly back to DF from Caracas, the end of your trip. I am only guessing about your itinerary.