Have you considered hosting your embassy section on another domain name with the keywords? It will take some time, but you could probably rank with some organic SEO for phrases like "how to apply for visa to france from london" by blogging.
I can see how I can focus on that one niche and become profitable, but wouldn't that be spreading myself thin over two projects instead of one big one?
I can understand you don't want to spend too much time over this. Can't you automatically generate static pages listing the key information given the user's destination, origin and nationality? I'm guessing the embassy information doesn't change too often, so having static content will help with SEO and caching.