Seems like Google map is hardcoded in single contact page? If so, how can the template be modified to get rid of this map?

No help to get here, obviously. I'll answer my own question:
In templates/sj_basic4/html/com_contact/contact/default.php
remove line 93-95 with the text:
<div class="map col-lg-12">
<iframe width="100%" height="400px" frameborder="0" src="www.google.com/maps/embed?pb=!1m18!1m12!1m3!1d211642.2952567641!2d-118.41173249999999!3d34.020498899999986!2m3!1f0!2f0!3f0!3m2!1i1024!2i768!4f13.1!3m3!1m2!1s0x80c2c75ddc27da13%3A0xe22fdf6f254608f4!2sLos+Angeles%2C+CA!5e0!3m2!1sen!2s!4v1402372564534" style="pointer-events: none;"></iframe>
</div>

Dear kimborg,

Good job. If you need any help, please contact us via ticket.

Thanks