How did scientists discover the concepts of anode and cathode without knowing about electrons?
Electricity is a macroscopic phenomenon. It does not depend on the notion of an electron.

In 1733 Charles François de Cisternay du Fay discovered the existence of positive and negative charge. In 1800, after the invention of the voltaic pile, the first electrolysis experiments that showed the effect of electric current on water have been made.

In 1833 Michael Faraday defined the terms cathode and anode:


  The anode is therefore that surface at which the electric current, according to our present expression, enters : it is the negative extremity of the decomposing body; is where oxygen, chlorine, acids, &amp;e., are evolved; and is against or opposite the positive electrode. The cathode is that surface at which the current leaves the decomposing body, and is its positive extremity ; the combustible bodies, metals, alkalies, and bases, are evolved there, and it is in contact with the negative electrode.


His definition does not involve particles of any type. In fact Richard Laming firstly hypothesized the concept of an indivisible quantity of electric charge in 1838.

You may want to study https://en.wikipedia.org/wiki/History_of_electrochemistry for further information.