504 Gateway Timeout - Two EC2 instances with load balancer

First, what is the Idle Timeout for your ELB set to? You'll find it at the very bottom of the "Description" tab for your load balancer. You can read more about the idle timeout here in the ELB documentation. The default is 60 seconds. You should also consider setting or increasing Keep-alive in your web server. How you do that will depend on what web server you are using.

Second, if you think it's due to the client being switched from one instance to the other then you should enable session stickiness in the ELB. This will ensure that a client is always directed to the same back-end instance by the load balancer. To enable this, again go to the "Description" tab then click on the Edit link next to each entry in the Port Configuration section. You'll likely want to choose the "Enable Load Balancer Generated Cookie Stickiness" option since that will tell the ELB to manage all aspects of the stickiness.

What web server are you using? I had a very similar issue with nginx and AWS load balancing. I added keepalive_timeout 75s; to the http block in my nginx config file and haven't see the issue since.

Make sure you restart nginx after you add and save that line (on ubuntu sudo service nginx restart. On redhat stop nginx /path/to/nginx/executable -s stop then /path/to/nginx/executable to start up nginx)

This fix was recommended by AWS on their help page AWS Load balancer troubleshooting