You must first create the Contact and then once you know its primary key then create the Patient and reference the contact with the PK you now know. Or if the FK in the Patient table is nullable you can create the Patient first with NULL as the ContactId, create the contact and then update the Patient but I wouldn't do it like this.
The idea of foreign key constraints is that the row being referenced MUST exist therefore the row being referenced must exist BEFORE the row referencing it.
If you really need to be able to have the same Contact for multiple Patients then I think it's good db design. If the relationship is actually one-to-one, then you don't need to separate them into two tables. Given your examples, it might be that what you need is a Person table where you can put all the common properties of Doctors, Teachers and Patients.
EDIT:
I think it's inheritance what you are really after. There are few styles of implementing inheritance in relational db but here's one example.
Person database design
PersonId in Nurse and Doctor are foreign keys referencing Person table but they are also the primary keys of those tables.
To insert a Nurse-row, you could do like this (SQL Server):
INSERT INTO Person(FirstName) VALUES('Test nurse')
GO
INSERT INTO Nurse(PersonId, IsRegistered) VALUES(SCOPE_IDENTITY(), 1)
GO
EDIT2:
Google reveals that SCOPE_IDENTITY() equivalent in mysql is LAST_INSERT_ID() [mysql doc]
EDIT3:
I wouldn't separate doctors and nurses into their own tables so that columns are duplicated. Doing a select without inner joins would probably be more efficient but performance shouldn't be the only criteria especially if the performance difference isn't that notable. There will many occasions when you just need the common person data so you don't always have to do the joins anyway. Having each person in the same table gives the possibility to look for a person in a single table. Having common properties in a single table also allows you have to have doctor who is also a patient without duplicating any data. Later, if you want to have more common attributes, you'd need to add them to each "derived" table too and I will assure you that one day you or someone else forgets to add the properties in one of the tables.
If for some reason you are still worried about performance and are willing to sacrifice normalization to gain performance, another possibility is to have all person columns in the same table and maybe have a type column there to distinguish them and just have a lot of null columns, so that all the nurse columns are null for doctors and so on. You can read about inheritance implementation strategies to get an idea of even though you aren't using Entity Framework.
EDIT4:
Even if you don't have any nurse-specific columns at the moment, I would still create a table for them if it's even slightly possible that there will be in the future. Doing an inner join is a pretty good way to find the nurses or you could do it in the WHERE-clause (there a probably a billion ways to do this). You could have type column in the Person table but that would prevent the same person being a doctor and a patient at the same time. Also in my opinion separate tables is more "strict" and more clear for (future) developers.
I would probably make PersonId nullable in the User table since you might have users that are not actual people in the organization. For example administrators or similar service users. Think about in terms of real world entities (forget about foreign keys and nullables), is every user absolutely part of the organization? But all this is up to you and the requirements of the software. Database design should begin with an entity relationship design where you figure out the real world relationships without considering how they will be mapped to a relational database. This helps you to figure out what the actual requirements are.
