This is possible but you'll still need to have 2 records on the database for each line (origin and destination). Example 2 here describes the steps to follow: http://onlinehelp.tableau.com/current/pro/desktop/en-us/help.htm#maps_howto_origin_destination.html?lang=en-us. Instead of dragging latitude and longitude to the view (which your data set won't have), you'll drag the Country/City fields that are recognized as Geographical data by Tableau. You'll notice when you drag them, an auto-generated latitude and longitude appear! Other than that, it's the same process.
Hope this helps!