Building a frugal dumpster/secondhand singlespeed or fixed gear is definitely one of those tasks that has become much more difficult with their growth in popularity.
So, let's say you've found a frame that's in your relative size range. You've figured this out already by riding other bicycles and visiting bike shops and figuring out a rough range of acceptable seat tube and top tube lengths. And you obsessively carry around a metric tape measure (probably not that hard in Europe).
The first thing to check when selecting a frame is its suitability for conversion. For a fixed gear or singlespeed without chain tensioner that means it needs to have horizontal dropouts or track ends. (Expensive options like an eccentric bottom bracket or sliding dropouts would work here as well, but those are rare to find on inexpensive frames.)
The next thing to consider is completeness relative to your parts supply. A frame with fork is almost always better than a bare frame - finding compatible road forks, particularly threaded, can be annoying as there are a number of odd old sizes out there. If you've got no parts to start with, a complete bike makes a good base point. Singlespeeding a complete bike is relatively trivial - remove the chain, remove the shifters and derailleurs, and then shorten the chain and reinstall it over your preferred gear combination. As you find additional parts you like you can replace them piecemeal.
As far as damage goes, the main stress points to look at are going to be where the rear dropouts meet the chainstay and seatstay and where the seatstays meet the seat tube. But give it a quick gander at all the joints to look for any obvious cracks. You'll also want to check just behind the headtube for any sign that the bike has been in a front end collision or roof rack crash. In general, any kind of bunched-up paint is usually a sign of a bent tube and a compromised frame.