Some possible causes for your problem:
Damaged wiring from starter relay to starter
Damaged wiring from battery to starter
Damaged wiring from ignition lock to starter relay
Broken starter relay
3 and 4 could be possible because the relay click you are hearing could come from a different relay. There is a relay in some cars to turn off other power loads like the radio to reduce the load at the battery during engine start.
Broken Starter
Dead battery
You said you checked the battery, so this is just for completeness. If the clicking sound you are hearing is a continuos repeating clicking while holding the key in 'start' position, it could come from a dead/weak battery. Some modern cars (mostly VAG but maybe also others) refuse to start when the battery is to weak. Instead you hear a repeating clicking sound.
- Some problem with the anti-theft system
Usually some light in the dashboard should light up in this case.