גרשטיין נולד בבית חולים העמק ליד עפולה לשולה (קישיק) שעלתה מסוריה ורפאל גרשטיין שעלה מארגנטינה. היה הבכור בין שלושה ילדים. גדל והתחנך בקיבוץ רשפים, וכילד התעניין בטבע, ארכאולוגיה וגאוגרפיה של ארץ ישראל. למד בבית הספר היסודי ברשפים ובתיכון למד במוסד החינוכי גלבוע בתנאי פנימיה עם נערים מקיבוצים אחרים. כנער, עבד גרשטיין בענף מִדְגֶּה של הקיבוץ. טרם גיוסו התנדב לחצי שנת שירות בקיבוץ הראל.
בינואר 1979 התגייס לצה"ל והתנדב לשרת בשייטת 13 ("הקומנדו הימי"). אחרי שנה הודח מן השייטת ועבר לשרת בחטיבת גולני. בשלשת החודשים הראשונים שירת בפלנ"ט, ולאחר מכן עבר לסיירת גולני. בסיירת עבר מסלול הכשרה כלוחם, קורס מ"כים חי"ר ולקח חלק באימונים ופעילות המבצעית במסגרת הסיירת והחטיבה. לאחר שסיים בהצטיינות קורס קציני חי"ר, מונה למפקד צוות בסיירת גולני עליה פיקד במבצע שלום הגליל. גרשטיין הוביל את הצוות בפעולה לכיבוש הבופור, נפצע קל בזרועו אך המשיך להילחם. בתום הקרב פונה לבית חולים, אך כעבור יומיים התעקש וחזר אל יחידתו בלבנון. ב-פברואר 1983 השתחרר מצה"ל כסגן מפקד פלוגה. בתקופת האזרחות השתלב בעבודה בקיבוץ, והיה לסדרן רכב. ביוני 1983 יצא לטיול תרמילאים באמריקה הצפונית והדרומית עם חברתו וחזר לאחר כשנה לארץ, התגייס לשב"כ אך במהלך ההכשרה החליט שאיננו רוצה לעסוק בתחום הזה.
באוגוסט 1985 בעקבות קול קורא של מח"ט גולני צבי פולג, חזר לשירות בקבע ופיקד על פלוגה בגולני בגדוד 12.
בתפקידו זה שקד על העלאת רמת החיילות והכושר הגופני והפך את הפלוגה לאחת מהטובות בחטיבה. בתפקידו הבא שימש קצין המבצעים של חטיבת גולני, ב-1987 מונה למפקד סיירת גולני, ופיקד על פעולות נועזות ברצועת הביטחון בלבנון. באחד המבצעים ביצע כוח בפיקוד מפקד חטיבת גולני דאז, אל"ם גבי אשכנזי, פשיטה על בסיס חזבאללה שמוקם בחווה חקלאית המכונה מזרעת אל- חמרא שברמת נבטיה. כוח החוד, שהורכב מאנשי הסיירת, בפיקוד של גרשטיין, נע בחשאי עד שהיה בקרבתם של המחבלים והרגם]. תחת פיקודו של גרשטיין לקחה הסיירת חלק במבצע "כחול וחום", בו הייתה למעשה, הכוח היחיד שהשלים את משימתו ופגע במספר רב של מחבלים מחד, ולא ספג נפגעים מאידך.
בשנת 1989 מונה למג"ד - מפקד גדוד 51 של גולני והוביל אותו בפעילות מבצעית בלבנון כנגד מחבלי החזבאללה. אז גם עבר לגור עם חברתו, הרטל, בקיבוץ יגור. בשנת 1991 מונה למפקד גדוד 17 בביסלמ"ח. במהלך כהונתו כמ"פ ומג"ד שם דגש על חינוך, ובפרט על חינוך לאהבת והכרת ארץ ישראל. בשנת 1993 הועלה לדרגת אלוף משנה ומונה למפקד חטיבת הגזרה המזרחית של יחידת הקישור ללבנון (יק"ל) שם נאלץ לטפל גם בבעיות האוכלוסייה האזרחית בנוסף למלחמה עיקשת במחבלים. במהלך תפקידו למד ערבית וכונן יחסים טובים עם המקומיים. גם כמח"ט הקפיד ארז להיות בחזית הלחימה, הוביל כוחות ברצועת הביטחון, ובאחד המקרים הרג שני מחבלים בסמוך לג'בל א- רפיע. בשנת 1994 יצא ללימודים במכללה לביטחון לאומי ובאוניברסיטת חיפה, וסיים תואר ראשון במדע המדינה.
באוגוסט 1995 מונה למפקד חטיבת גולני. באותה שנה התחתן עם הרטל ובנה את ביתו במושב היוגב. ב-1997 נולד בנם עומר. גרשטיין בלט כמפקד החטיבה בהפעלה מקורית של סיירת החטיבה במבצעים מיוחדים כנגד החזבאללה בלבנון. בסמוך למועד סיום תפקידו כמפקד החטיבה אירע אסון השריפה בוואדי סלוקי, בו נהרגו חמישה מלוחמי החטיבה ונפצעו חמישה נוספים. לאחר מכן שימש סגן מפקד עוצבת געש בשנים 1997-1998, ב-1998 הועלה לדרגת תת-אלוף ומונה למפקד יחידת הקישור ללבנון. בתקופה זו התנהל מאבק אזרחי בהנהגת תנועת ארבע אמהות כנגד הישיבה בלבנון, וגרשטיין התבטא בפומבי נגדן ואמר כי ההפגנות בישראל יוצרות איום על החיילים, מכיוון שהן מעודדות את החזבאללה.
ב-28 בפברואר 1999 (י"ב באדר ה'תשנ"ט) נהרג גרשטיין ממטען צד של חזבאללה שהופעל לעבר מכונית המרצדס המשוריינת שבה נסע בקרבת מוצב כאוכבא ברצועת הביטחון ליד צומת סוק אל חאן, לאחר שחזר מביקור של ניחום אבלים בביתו של איש צד"ל שנהרג, בכפר הלבנוני שבעא. השיירה נסעה לכיוון מפקדת עוצבת לבנון במטולה. בפיצוץ, שגרם להתהפכות המכונית, נהרגו גם נהגו רס"ב עימאד אבו ריש, קשרו סמ"ר עמר אל-קבץ וכתב קול ישראל בצפון אילן רועה, שהתלווה אל גרשטיין למשימת סיקור. מותו של הקצין הבכיר בלבנון, היה הגורם האחרון ליציאת צה"ל מלבנון במאי 2000. ברק המועמד לראשות הממשלה אמר במהלך מסע הבחירות שלו שיפעל עד יוני 2000 ליציאת צה"ל מלבנון.
גרשטיין הובא למנוחות בבית העלמין בקיבוץ רשפים.
אנדרטה לתא"ל ארז גרשטיין בבסיס ביסל"ח 17 בו שימש ארז בעבר כמפקד גדוד
גרשטיין נהג, בכל שירותו בצה"ל, להסתובב ללא רצועה לנשק, כשרק ידו מחזיקה בנשק, כדי "להיות מוכן תמיד". כאשר היה מ"פ בגדוד 12 של גולני חייב את כל פלוגתו בטירונות ללכת עם הנשק במצב[דרושה הבהרה] של מוכנות לקרב. בהשפעתו נוהגים הטירונים בחטיבת גולני לשאת את נשקם ללא רצועה במהלך ראשית פרק הטירונות. ידיעת הארץ הייתה מאוד חשובה לו. בכל מקום חדש שהגיע עם חייליו, טרח להסביר להם מהו האזור והיישובים שקיימים בו. לעתים היה מוכן לוותר על אימונים צבאים בשביל ללמד על אזור מסוים, ואף אמר "החינוך זה האימונים". כאשר פלוגתו הגיעה למשימות בט"ש בחזית רמת הגולן, הבטיח שבוע חופש ("רגילה") לכל מי שילמד בעל פה את שמות כל היישובים היהודים בגולן. והעניק את החופש לשניים מהחיילים שהצליחו במשימה.
כמח"ט גולני אסר על הפקודים שלו להשתטח על קברי חבריהם. אמר שיש לכבד את זכר הלוחמים בעמידה, ומי שכואב לו שילך לנחם את משפחות הנופלים שלהם הרבה יותר כואב. חינך את חייליו לחתירה למגע, ואף טען שהמסתערים תמיד מנצחים. קצינים רבים העידו על הנחישות שלו לבצע תרגילים ומשימות, כאשר התנאים נעשים קשים מדי והם נטו לוותר ולהפסיקם. גרשטיין נחשב לאורך תקופת שירותו לסמל ולמודל בעבור החיילים אשר שירתו בלבנון. קצינים רבים העידו לאחר מותו כי השפיע עליהם עמוקות ובהם תא"ל משה (צ'יקו) תמיר שייחד לו פרק בספרו מלחמה ללא אות.
לזכרו הוקמו מפעלי הנצחה שונים ובהם שיקום שביל טיול בנחל יצפור שבהר הגלבוע, ונקרא על שמו בניין מחלקת הנוער והצעירים במועצה האזורית עמק יזרעאל.