This is a stub of an answer which will be added to as I find more resources. I'll write out a Research Plan to give you some ideas. You may have done a lot of this already, and if you have, feel free to add to your question. But I'll start from scratch, so the information may also help someone coming along later. Since you asked specifically about Jewish records, I'll assume you already know that 1812 is too early for civil registration in that area.
Make a Research Plan
If you haven't already done so, make a timeline for your grandfather's life and add events as you find out about them, with a note about the source of the information. This will allow you to work backwards from your known event of the first son's birth in 1837 in Vienna, back to when he first entered the country.
You already have at least one source that says he was born in Reca, but you can look for others. Sometimes people move to another town when they were very young, then are known as "from" that second place, and eventually people assume they were born there, when they were actually from another town close by. Sources of Genealogical Information is a useful checklist that says where you might find information about someone's birthplace. One important source missing from their list for birth places is Naturalization Records. If your grandfather was Naturalized or had to register when he came to Vienna, those records might give the place he lived in before he came to Vienna.
Also, sometimes filling in a person's early life, without specifically looking for their birth place, can reveal information you weren't expecting. School enrollment records in England sometimes say whether a student transferred from another school. This can be a clue about when a family first moved into the area.
If your grandfather had siblings, their records also can fill in the picture of the family's history, and give pointers to places where you can find other clues.
Keep notes about the specific record groups you searched and explore the reasons why you didn't find anything. This allows you to keep two separate lists -- one, records that you won't find because they were not created in that time period, like the civil records, and two, the ones that you might be able to find but you don't know where to find them yet, like the church records. It also helps to keep a list of the exact search terms you used, since surname spellings can vary.
Finding Slovakian Records
The FamilySearch Wiki article about Slovakia has a set of guidelines about getting started doing research in Slovakia, and how to find records there. In their article Beginning Slovakian Research, see the section marked Determine the record keeping jurisdiction, where it says:
Not every village in Slovakia had its own parish. Often, several
smaller villages belonged to one parish. Use gazetteer to determine
the location of the parish or synagogue where records were kept. Once
you have determined the location of the church or synagogue, use the
FamilySearch Catalog to get the film numbers of the available records.
You can then order the appropriate films.
The article Slovakia Gazetteers lists some of the resources you can use to help find out what synagogue might have records for someone from Reca.
It is useful to keep a list of the specific searches you have made already, with a note to yourself about why you did not find anything. For example:
This record contains images of baptisms, births, marriages, and
burials from 1587 to 1910, and contains records that occurred in the
Roman Catholic, Evangelical Lutheran, and Reformed Church parishes, as
well Jewish congregations in Slovakia. Included are records from
selected archives in Bytča, Bratislava, Košice, Levoča, and Prešov.
Records from other archives will be added as they become available.
So it may be that a website didn't have any records from Reca at the time you first searched, but more records may show up online later.
While you are waiting for a more specific answer, you might find some clues in the related question How can I determine what records are available in a particular locale?
Update: seen on a recent 'new records' news item posted by the website Genealogy In Time:
The [genealogy] website GenTeam currently has over 11 million records from Austria
and surrounding countries. It covers most of the former Austro-Hungarian
Empire .... The website is in English. Access
is free upon registration.