So to answer my own question:
I installed a turn Server and now everything works fine.
Here is a quickl guide what i did to install the reTURN server on ubuntu 14.04:
1) apt-get install resiprocate-turn-server
2) nano /etc/reTurn/reTurnServer.config
3) Set up IP and Port for TURN Server in config
4) Disabled md5 PW hash
5) Added User in nano /etc/reTurn/users.txt like username:SHA1HASHOFPW:reTurn:authorized
6) Configured IP-Tables to open up the Port
7) Restart server so the new configuration becomes active: service resiprocate-turn-server restart
8) In Construct 2 before opening the connection: Multiplayer: Add ICE server "TURN:domain.my(username "username", "credential SHA1HASHOFPW"
9) Works like a charm on all devices now.
If anyone needs an account for testing purpose i can grant you a timly limited access to my TURN-Server, so you can test your stuff out!
Kind regards
Patrick