How do you know which atoms are in a specific piece of matter? If you have a piece of matter in front of you, how can you know of which atoms it consists? And starting from nothing, how can I discover all the elements (or just a lot of them) of the periodic table? 
I can imagine some unefficient methods based on atom's characteristics (e.g. heat the matter till it becomes a gas, then calculate it's spectrum; weigh and compare pieces of the matter very accurately to "discover" the quanta of mass; ...), but all those methods seem quite theoretical/impossible. Moreover, when people started tabling the atoms (end of the 19th century), things like the spectrum of an atom weren't even known yet. 
Or is it all done by chemical reactions, and then comparing the ratios of the compounds and their masses? This seems for me the most obvious way to tackle the problem, although it still looks like a very hard job to determine all possible elements like that experimentally (>100 years ago, or even now if I had to do it myself in some kind of way). I cannot imagine having all the elements in my daily neighbourhood right know, to start experimenting with them and "discovering" them.
Measuring characteristics like the boiling point etc. doesn't seem to be a good idea either, because you don't know whether you're dealing a mono-atomic specimen or a compound.
So my question is actually twofold: how did people manage to discover them more than 100 years ago (historically), and how can I do it myself now (practically)?
 A: 
So my question is actually twofold: how did people manage to discover them more than 100 years ago (historically),

Historically there are many different ways people discovered different elements, and many ingenious ways of proving that they were actually elementary. One of the most useful and revolutionary was the discovery of Electrochemistry. Where electricity can be used to chemically separate molecules, such as the Hofmann voltameter which can separate water into its component atoms $H_2 O \to 2H+O $
All of the techniques you mention would have to be performed every time you discover a new element / compound but since we already know its properties and just want to know if it is present we can use modern approaches.

and how can I do it myself now (practically)?

There are many techniques (both destructive and nondestructive) used today to tell the composition of a compound. It helps if you have an idea of what it is before you begin, I.E. if it is a crystal, is it an organic compound, etc.
There is the branch of science called Spectroscopy that uses spectrometers to send light into a compound and tell its composition based what and how much light is reflected / transmitted. Eg. here is the unique spectral "fingerprint" for helium based on the electron energy levels in helium. The same technique can be used to tell compounds by the spectra fingerprint of their chemical bonds.
For crystals X-ray crystallography can be used to infer the crystal structure of a material.
If you want to actually perform these experiments yourself (I would recommend Mass spec. as XRD has x-rays which are dangerous), you can make your own setup reasonably easy and inexpensively, all you need is a laser, diffraction grating, and sensor (if you are very careful you eye is a very sensitive sensor in a dark room, don't ever shine a laser directly at your eye $\large{Ever}$), or buy one off the internet.
A: Take your lump, hit it with an x-ray or e-beam.  See how it fluoresces (and absorbs, for the x-rays),
http://alloytester.com/XRF-alloy-analyzers-2?gclid=CPuJzaSF27wCFYRQ7AoduSgAHg 
   From Mg to U, hand held. 
http://en.wikipedia.org/wiki/Extended_X-ray_absorption_fine_structure 
If you want structure as well as composition, it gets complicated.  If you want functional structure, it is more complicated still.  The difference among p-, i-, and n-type silicon is parts per billion doping of the ultrapure matrix. 
In 1900 it was wet chemistry.  There were no electronics.  Diffraction gratings were mechanically ruled and very expensive, largely leaving prisms.  Aspirate your stuff into an arc, get composite emission spectra on photographic film, tease it out by eyeball and hand.  Obtained spectra were calibrated against iron emission.   Atoms where hypothetical in 1900.

