How would I need to change ElectrumX to use FIFO selection of UTXOs? By default, UTXOs are picked randomly in ElectrumX. I want to change this behaviour and spend UTXOs on 'FIFO' basis. What changes do I need to make?
By default, UTXOs are picked randomly. 


You mean in Bitcoin Core's wallet? No, they're not picked randomly. There are a number of strategies, but in general the aim is to avoid change if possible, avoid transaction outputs with few confirms if possible, and otherwise create a match close to the amount intended to be sent.


  My want to change this behaviour and spend UTXOs on 'FIFO' basis. What changes do i need to make?


That's possible - the wallet already knows the timestamp when transaction outputs were created, so you don't need to make any changes besides changing the coin selection algorithm. In particular, you don't need to add timestamps to UTXOs.

However, FIFO isn't known to be a very good strategy. Mark Erhardt's thesis does a comparative study to analyse various coin selection strategies. There is ongoing work in Bitcoin Core to adopt some of the outcomes of this research, some of which is already completed. In particular, the master branch as of writing (April 2018) includes the Branch and Bound strategy for change avoidance.