What is the easiest way to check what was the balance of address X at block Y? (without 3rd party services)
As you have rightly mentioned getreceivedbyaddress does not return a value for non node addresses, i.e. the addresses which are not in your nodes wallet. 

txindex=1 in the configuration file followed by restarting bitcoind with -reindex parameter creates indexes for all the txs so that you can open them up with getrawtransaction and check the details inside the transaction.

The only way you can check for the addresses balance at any given block is to crawl all the blocks before the block under consideration and check each transaction's vout whether it contains the address under consideration. Also you will have to check whether any of the vouts you just went through have not been spent which would decrease the balance accordingly.