How exactly do I extract the important features from strings for machine learning?
(1) How exactly do I go about extracting information from the Ad topic line?

The best way to deal with the test string is to Convert it into a term-document matrix and calculate the TFIDF Scores for every word in the string.

(2) How should I approach the categorical variables Country and City? ( I've heard about encoding but won't a large number of countries/cities be a problem?)

Yes you said the right large number of cities will be a problem i suggest still you can go with that, Rather there is a way find out the distribution of all your cities and cities and convert them into integers.
Even another way could be give weights to the cities which are repeated most,let me give you an example:

Suppose you have 10 observations and 5 cities A(5 times),B(2 times),C(once),D(Once),E(Once):

so A will get a weight of 5/10=0.5 which B will get a weight of 2/10=0.2 and so on.

Hope this helps!