You can bow to give respect as long as your niat is right. To bow is not to sujud. You can also do so to a certain comfortable angle that is appropriate in budo.
Whilst some may insist that your body be parallel to the floor, most people don't mind that you decrease the angle to say 45 degrees instead.
Kneeling down has no religious connotations. You do not kneel down to worship, you kneel to show your respect. Same as you would if an elder sits on the floor, you sit on the floor though you may prefer the chair.
Lastly, your sensei is a religious man. Ask him to pray for guidance. Opinions here do not matter as such.
This is incorrect. Please check your inbox.